用线段树维护树的直径

目的

  有时候我们需要快速回答一棵子树的直径，或者去掉一棵子树后形成的树的直径。普通的找直径方法是两遍 bfs，时间 $O(n)$，这里的方法用 $O(\log n)$ 的时间回答。

操作

首先

  我们做出一棵树的 dfs 序，然后以 dfs 序为轴建立线段树，每个区间维护直径 $len$，以及直径的两个端点 $x$ 和 $y$。
  会有这么一个问题：你按线段树划分区间，那一个区间内的点可能不连通啊！！！其实没问题的，因为我们最后询问的是一棵（子）树，意思是我们询问的东西肯定是连通的。所以操作时候不联通你就当它连通就好啦。
  还会有这么一个问题：直径可能不止一条啊！！！随便记录一条即可，下文解释。

最关键是这个合并

  区间内只有 1 个点的时候 $len=0$，$x,y$ 等于自己。
  现在考虑区间的合并。左区间有两个直径端点，右区间也有两个直径端点，这四个点中的最远点对，就是新区间的直径。
  注意我们这里用的距离是原树的距离（已经说过我们强行让一个区间的点是连通的了）。

  简单证明一下。
  我们看作是 $x$ 所在的连通块通过边 $(x,y)$ 连向 $y$ 所在的连通块。
  若新直径不经过 $(x,y)$ ，则就是原来的两条直径取 $\max$。
  若新直径经过 $(x,y)$ ，就要考虑 $x$ 延伸到哪儿、$y$ 延伸到哪儿了。由直径的定义可知，$x$ 能走到的最远点之一是 $x$ 所在连通块直径的端点，$y$ 同理。因此这时新直径的两个端点都是旧直径的端点。

  （这个证明也适用于增量法求树的直径，即我给一棵树加一个新点，那么新直径必有一端点是旧直径的端点）
  （注意只能是树，普通图没有这些性质）

所以

  有了这个神奇的合并操作，我们就可以求树中任意一个联通块（子树或是去掉一个子树什么的）的直径啦！

注意事项

  我们求点对距离时会用到 lca，然而线段树已经有一个 $\log$ 了，如果碰到题目要卡两个 $\log$，就要用 rmq 求 lca。

例题

例题1 例题2