建站实战干货

考虑直径定义：

\[\max_{x\leq y}(d_x+d_y-d_{\mathrm{lca}(x,y)}) \]

我们发现问题难点在于维护 \(d_{\mathrm{lca}(x,y)}\)。我们考虑欧拉序求 \(\mathrm{lca}\) 的方法，即：

\[d_{\mathrm{lca}(x,y)}=\min_{\mathrm{any}_x\leq z\leq \mathrm{any}_y}(d_{e_z}) \]

那么我们发现原式可以转化成：

\[\max_{x\leq y}^{2n-1}(a_x+a_y-2\min_{x\leq z\leq y}(a_z)) \]

其中 \(a_i=d_{e_i}\)。那么我们考虑线段树维护这个东西，对于边修改则就相当于是对于一个子树的 \(\mathrm{dep}\leftarrow \mathrm{dep}+v\)。区间加即可。