CF1787G Weighed Tree Radius

CF1787G Weighed Tree Radius

前言：

NGC5457 发现这道题的题目名字打错了，应用 "Weighted" 而非 "Weighed"。

首先将“半径”转化为求直径的一半，这样考虑的东西就是不带有方向性的。

容易发现答案可以取到直径的一半上取整且不可能更小，树边全为 \(1\) 所以树上一定有这个点，若某条路径的中点不在树上，那么半径就是较长的那条路径。

两种不同的做法：

做法一

发现这个问题是“加入一个点好更新答案，删除一个点不好更新答案”的问题：

加入一个点直接查询该点和目前直径的两个端点，新的直径要么是原本的直径要么是某个端点和新的点的连线，直接处理就行了。

因为不好删除且可以离线，我们使用线段树分治，在加入每个点的时候维护直径并更新答案。

查询距离需要在原树上求 LCA，所以需要离线把原树建出来。
使用 dfs 序和 RMQ 求 LCA，时空复杂度均为 \(O(n\log n)\)。

优点是可以扩展到连边断边的情况，缺点是码量和常数都较大，且空间复杂度高。

做法二

考虑一条带权的非退化为点的路径的权值对应的值是 \(dep_u+a_u+dep_v+a_v-2dep_{LCA}\)。

根据 dfs 序求 LCA 的结论，LCA 一定是 dfs 序在 \(u,v\) 之间最浅点的父亲，所以上面那个式子可以看作 \(dep_x+a_x - 2 dep_y+2+dep_z+a_z(x<y\leq z)\)，因为我们要求该式子的最大值，所以 \((x,z]\) 之间的点只会比 LCA 深，不影响答案。

使用线段树维护上面那个式子就行了，其形如 \(a_x+b_y+c_z(x\leq y\leq z)\) 所以可并。

时间 \(O(n\log n)\) ， 空间线性。

优点是常数小，好写，空间线性，缺点是可扩展性低。