2025.1.7 做题记录
CF600Edsu 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)\)。
代码
#define ls(x) (x1; if(l=l&&tr.r>1; if(l1; if(x 过来提前占个楼 鼓励转贴优秀软件安全工具和文档！ 用心讨论，共获提升！ 不错，里面软件多更新就更好了 东西不错很实用谢谢分享 分享、互助 让互联网精神温暖你我 感谢分享，学习下。 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢，下载保存了 谢谢分享，辛苦了 不错，里面软件多更新就更好了 感谢，下载保存了 感谢发布原创作品，程序园因你更精彩 谢谢分享，试用一下 yyds。多谢分享 热心回复！ 懂技术并乐意极积无私分享的人越来越少。珍惜 鼓励转贴优秀软件安全工具和文档！ 感谢分享，学习下。
页:
[1]
2