P9665 [ICPC2021 Macao R] Colorful Tree 题解

· · 题解

CNBLOGS

我永远喜欢数据结构。

题目传送门

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

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

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

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

本文中，点对 (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] 内维护两个信息：

第一个信息也可以通过结论维护。第二个信息，考虑这个点对是否在同一半区间内，若是则拿左 / 右儿子的信息合并，否则一定是一个点的颜色 \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)。

提交记录 代码