【欧拉序】CF1192B Dynamic Diameter 笔记

欧拉序：访问一个节点的子树后，将这个节点的父亲加入 DFS 序的末尾构成的序列 $E$。

性质：

• 设 $E_l=u,E_r=v$，若 $x$ 满足 ${\mathrm{dep}}_x=\underset{i=l}{\overset{r}{min}}{\mathrm{dep}}_i$，则 $x=\mathrm{LCA}(u,v)$。
  • 由于 $u,v$ 分属于 $x$ 的不同子树，因此 $x$ 至少会在访问完 $u$ 所在子树之后加入序列；而 $u,v$ 同属 $\mathrm{fa}(x)$ 的子树，因此 $x$ 的祖先不会出现在 $E_{[l,r]}$。
• 与 DFS 序一样，一个子树内的全部节点位于序列上一段连续的区间。

回到本题，求直径相当于求 $\underset{u,v}{max}({\mathrm{dep}}_u+{\mathrm{dep}}_v-2{\mathrm{dep}}_{\mathrm{LCA}(u,v)})$，变换为欧拉序之后，相当于要在序列上找到 $l<\mathrm{mid}<r$，使得 ${\mathrm{dep}}_{E_l}+{\mathrm{dep}}_{E_r}-2{\mathrm{dep}}_{E_{\mathrm{mid}}}$ 最大，由于 LCA 是 $[l,r]$ 中深度最小的，因此总是能成为最优的 $\mathrm{mid}$。

接着变为经典线段树问题，push_up 时只需考虑跨过区间，即 $l,\mathrm{mid}$ 来自一边，$r$ 来自另一边；或 $l$ 来自一边，$\mathrm{mid},r$ 来自另一边的情况。因此还需要分别维护区间内 ${\mathrm{dep}}_{E_l}-2{\mathrm{dep}}_{E_{\mathrm{mid}}}$、${\mathrm{dep}}_{E_l}-2{\mathrm{dep}}_{E_{\mathrm{mid}}}$ 的最大值。

修改一条边即为增加一个子树内的深度，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。