自动搬运

查看原文

来自洛谷，原作者为

	lzyqwq 我永远喜欢数据结构。

搬运于2025-08-24 22:50:33，当前版本为作者最后更新于2023-12-01 16:25:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

CNBLOGS

我永远喜欢数据结构。

题目传送门

• 给出一棵树，初始只有一个点 $1$，其颜色为 $C$。

• 有 $q$ 次操作，分为两种类型：

  • $0\space x\space c\space d$，记当前树中一共有 $n$ 个点，新增一个 $n+1$，其父亲为 $x$，颜色为 $c$，两点间边权为 $d$。

  • $1\space x\space c$，将点 $x$ 的颜色修改为 $c$。

• 每次操作结束后，找到两个颜色不同的点，使得它们的树上距离最大。

• 多测，$\sum q\le5\times 10^5$。

• $\text{6.00 s / 512.00 MB}$。

本文中，点对 $(u,v)$ 可以满足 $u=v$。记 $Q=\sum q$。

可以先离线把树建出来，树上距离不变，因为两点间的唯一路径不变。

首先有个结论：

有两个点集 $S_1,S_2$，其中 $S_1$ 中距离最大的两个点为 $u_1,v_1$，$S_2$ 中两个距离最大的点为 $u_2,v_2$，则 $S_1\bigcup S_2$ 中两个距离最大的点 $x_1,x_2\in\{u_1,u_2,v_1,v_2\}$；在 $S_1,S_2$ 中各选一个点，使得树上距离最大的点 $y_1,y_2\in\{u_1,u_2,v_1,v_2\}$。

前者就是在后者的基础上考虑选取的两个点在同一个集合内。

因为可以证明调整之后一定不劣。我们考虑使用线段树维护。

首先对于每一种颜色开一棵动态开点线段树，维护区间 $[l,r]$ 树上距离最远的点对。可以通过上述结论合并信息。

其次维护一棵线段树 $T$，区间 $[l,r]$ 内维护两个信息：

• 在 $[l,r]$ 颜色中的最远点对。

• 在 $[l,r]$ 颜色中不同色的最远点对。

第一个信息也可以通过结论维护。第二个信息，考虑这个点对是否在同一半区间内，若是则拿左 / 右儿子的信息合并，否则一定是一个点的颜色 $\le mid$，另一个 $>mid$。这等价于分别在颜色为 $[l,mid]$ 和 $[mid+1,r]$ 的点构成的点集中选一个点，使得树上距离最大。可以根据结论拿左 / 右儿子的第一个信息合并。

对于修改操作，若是加点 $u$，则在其对应颜色的动态开点线段树上，将 $u$ 对应的叶子的信息（点对）修改成 $(u,u)$。

若是改点 $u$ 的颜色，则在其原本颜色的动态开点线段树上，将 $u$ 对应的叶子信息修改为 ⌈空⌋，因为这个区间内不存在符合条件的点对。将新颜色对应的叶子的信息修改为 $(u,u)$。

每次对每种颜色的动态开点线段树维护好后，考虑 $T$ 的信息怎么变。显然只有涉及修改的颜色的叶子（及包含它的区间）发生了变化。

根据两种信息的定义，该叶子的第一种信息应该变为其对应动态开点线段树根上的信息，即这种颜色的最远点对。第二种信息应该变为 ⌈空⌋，因为显然不存在两个不同色的点。

还有一个注意点，求解 $\text{dis}(u,v)$ 的时候我们使用 $dep_u+dep_v-2\cdot dep_{\text{LCA}(u,v)}$。但是这里一次操作合并信息的次数可以到达 $\mathcal{O}(\log Q)$。而这题却出乎意料地卡了 $\mathcal{O}(Q\log^2 Q)$ 的做法。因此我们需要更快速的信息合并方式。

显然需要更高效地求 $\text{LCA}$。记 $f=\text{LCA}(u,v)$。那么记 $ed_x$ 为点 $x$ 子树中 $dfn$ 序最大的那个，显然有 $dfn_f\le dfn_u,dfn_v\le ed_f$。

特判掉 $u$ 或 $v$ 为 $f$ 的情况。我们记 $val_i$ 为 $dfn$ 序为 $i$ 的点的父亲的 $dfn$ 序。那么 $\boldsymbol{dfn_f=\min\limits_{i=dfn_u}^{dfn_v} val_i}$。此处默认 $dfn_u\le dfn_v$。

容易发现对于任意 $x$，$\forall \,i\in(dfn_x,ed_x],val_i\ge dfn_f$。你考虑 $x$ 一定能过通过不少于一条边向下走到这个范围内的点。

根据上面这个结论显然可以得到对于 $i\in[dfn_u,dfn_v],val_i\ge dfn_f$。因为 $[dfn_u,dfn_v]\subseteq (dfn_f,ed_f]$。

其次证明等号可以取到，因为 $u,v$ 一定在 $f$ 的不同子树内，由于 $dfn_u\le dfn_v$，所以 $u$ 所在子树先遍历，设 $v$ 所在子树的根为 $rt$，可以得到 $dfn_u\le dfn_{rt}\le dfn_v$。

你发现 $\boldsymbol{val_{dfn_{rt}}=dfn_f}$。

所以我们可以用 ST 表做这个 RMQ 问题，这样查询是 $\mathcal{O}(1)$ 的。

其次就是这题空信息的处理比较麻烦，可能需要较多特判。一种比较通用的方式是，对于信息我再记录一个变量 $e$，表示其是否为空。定义 $\oplus$ 为合并运算，若两个信息 $a,b$ 满足 $e_b=1$，则 $a\oplus b=a$。

事实上好像更麻烦。

这样一来，时间、空间复杂度均为 $\mathcal{O}(Q\log Q)$。

提交记录 代码