关于树的直径的瞎扯

不知道为啥，最近做到很多和树的直径相关的题目。在这里来记录一下各种 $\text{tricks}$。

树的直径，指的是树上最远的两个点之间的路径。若树上没有负权边，则可以通过两次 $\texttt{DFS}$ 求得其端点，否则可以简单地树形 $\text{dp}$。自然，一棵树可以有多条直径。

以下证明都很感性

在没有说明的情况下，一般认为树上边权为正。

直径的交

若一棵树有多条直径，那么他们必然有重叠部分。

考虑反证法。若存在两条不相交的直径，那么必然存在一条路径，连接两个直径上的两个点。那么只需要把两条“直径”拆成两块，然后两边都选更长的一侧，接上中间的路径，必然更优。

可用范围：在讨论直径的交集、多条直径的统一性的时候，可以考虑交点的特殊性质。

距离最远的节点

对于树上任意节点 $x$，令树上某一直径两个端点分别为 $\text{A,B}$，那么距离 $x$ 最远的节点必然是 $\text{A,B}$ 中的一个。
对于任意点 $x$，令 $c$ 为直径中点，那么 $d_x=d_c+\text{dis(x,c)}$。

假设现在选择了一个非直径节点 $y$，必然可以向某直径端点延伸使得答案更优。

直径的中点

直径的中点，往往具有十分优秀的性质：

任何点和直径中点的距离，必然不会超过 $\dfrac{\text{len}}{2}$。

这十分显然。用途十分广泛，可以认为 $\dfrac{\text{len}}{2}$ 是树的半径，那么任意点都不会超过这个半径的范围。在关于树上加点加边，与直径长度变化相关的问题上，是一个不错的思考方向。

令 $d_x=\max_{i=1}^n \text{dis(i,x)}$，那么直径中点是 $d$ 值最小的点（之一）。
对于任意点 $x$，令 $c$ 为直径中点，那么 $d_x=d_c+\text{dis(x,c)}$。

根据上述关于最远节点的性质，不难发现树的直径上点的 $d$ 值先减后增，非直径节点显然比不过直径上的点。因此直径中点 $d$ 值最小。

这个性质同样可以用来把直径中点作为根，然后一定有：

在以直径中心为根时，对于一个节点 $x$，其父亲的 $d$ 必然不大于 $d_x$。

这个可以用来做 CF516D Drazil and Morning Exercise。

直径的可加性

对于一棵树上的节点集合 $S_1,S_2$，若已经求得 $S_1,S_2$ 分别的直径端点 $\text{A}_1,\text{B}_1,\text{A}_2,\text{B}_2$。那么 $S_1 \cup S_2$ 的直径端点必然在 $\text{A}_1,\text{B}_1,\text{A}_2,\text{B}_2$ 中某两点取得。

也就是可以在 $\mathcal{O}(1)$ 之间内，对两个集合的直径信息进行合并。这启发我们使用数据结构来进行维护可加性：线段树维护区间直径等......

咕咕咕