CF600E
dsu on tree 裸题。
P3899
考虑对 \(a,b\) 的关系分类讨论。对于 \(\operatorname{LCA}(a,b)=b\) 的情况，那么 \(a,b\) 的公共后代肯定在 \(a\) 的子树内。即对于全部的 \((a,b)\)，其贡献为 \(siz_a-1\)。因为 \(dep_b +k \ge dep_a\)，所以 \(dep_b \ge dep_a-k\)，每个 \(b\) 的贡献为 \(siz_a-1\)。对于 \(\operatorname{LCA}(a,b)=a\) 的情况，那么 \(a,b\) 的公共后代肯定在 \(b\) 子树内。即对于全部 \((a,b)\)，其贡献为 \(siz_b-1\)。因为 \(dep_b-k \le dep_a\)，所以 \(dep_b \le dep_a+k\)，每个 \(b\) 的贡献为 \(siz_b-1\)。
那么问题就变成了，求 \(\sum\limits_{\operatorname{LCA}(a,b)=b\land dep_b \ge dep_a-k}^{} siz_a-1 + \sum\limits_{\operatorname{LCA}(a,b)=a\land dep_b \le dep_a+k}^{}siz_b-1\)。前者可以直接计算，因为 \(a\) 已知。后者拍到 DFS 序上就是区间内 \(dep\) 不超过 \(dep_a+k\) 的 \(siz-1\) 的和。可以直接主席树维护。时间复杂度 \(O(n\log n)\)。
P3703
染上一个没有染过的点比较麻烦。不如直接染成 \(x\)，因为点的编号不同，不愿能有两个 \(x,y (x\ne y)\) 进行操作 \(1\) 得到了相同的值，且仅可能有 \(x\) 到根的路径上存在这个颜色。那么对于求 \(x\) 到 \(y\) 的路径价值，我们就可以树剖维护。对于线段树维护其左端点的颜色，右端点的颜色，这个区间的价值。归并的时候只要相邻的颜色有重复，说明颜色段需要 \(-1\)。对于查询 \(x\) 子树内点到根价值最大值，因为我们相同的颜色肯定是一个点到根路径的前缀。那么当我们进行赋值操作的时候，可以维护出每个颜色的起始位置与尽头位置。当我们将 \(1\) 到 \(x\) 的路径覆盖时，一个完全被覆盖的颜色 \(c\) 就会对其子树的颜色产生 \(-1\) 的贡献。由于每个颜色最多被删除和添加共 \(O(n)\) 次，所以暴力维护即可。
我们将两个问题分开考虑。第一个使用树剖维护颜色段，第二个使用普通线段树维护区间最大值。时间复杂度 \(O(n\log^2 n)\)。
代码
[code]#define ls(x) (x1; if(l=l&&tr.r>1; if(l1; if(x |
