我永远喜欢数据结构。
给出一棵树，初始只有一个点 \(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)\)。