CF1192B Dynamic Diameter

题意：给出一棵 个点的带权无向树。

支持修改某条边的边权，并回答树的直径。

强制在线。，边权均为正。

---

• 欧拉序：dfs 遍历某棵树，每次经过某点时，将其写入欧拉序。

某个点将会被加入度数次,根节点会额外多一次,欧拉序的总长就是 的。

我们设点 第一次写入欧拉的位置是 ,可以视作类似dfs序的东西。

然后有一条很好的性质 :

• 一定在 中出现,且是深度最小的那个点。

  显然一定都在 的不同子树中。

  所以,遍历完 之后,回溯到 才能向下达到 ,这样就保证了 的出现。

  其次,访问到 时,现在对 子树的访问还未结束,不可能涉及到更浅的点。

  附 : 如果这张图有负权边,该结论就不成立,因为可能儿子比祖先“浅”。

接下来,我们观察路径长度的计算式:

放到欧拉序上看,就变成了:

这就是一个序列问题,考虑线段树维护。上述式子最大的对子 ,即为直径。

对于一个区间 :

设 为区间 最小值, 为最大值。

为 的最大值。也就是只有左半边两个点。

为 的最大值。也就是只有右半边两个点。

为区间内最大的直径。也就是三个点都全了。

设我们合并的两个线段树节点为 。

当转移时,最大的直径可以取左侧,可以取右侧,也可以跨越左右。

有两种方式跨越:

• 在左边 :

• 在右边 :

容易感知最优解一定是其中一种。

可以两端都在左侧 ,也可以两端都在右侧,取 。

此外,还可以一端在左侧,一段在右侧,即为 。

的处理方法类似。 的处理方法是经典的,不再赘述。

而我们的修改操作可以视作对一颗子树的 加上某个值。

可以转为区间加,只需要把对应的值按照端点个数改改就好,具体见代码。

综上,即可在 的复杂度内完成。

不到20min就写完了,可以说还是非常小清新的。(然而数组开小交了两次qwq)