树的中心和直径
Definition
链：满足与任一结点相连的边不超过 2 条的树称为链
树的直径：树的直径，是指树上最长的一条链
树的中心：以树的中心为树的根时，树的高度最小
Property
以树的直径上某点作为根时，将树的直径分为两条从根节点到叶节点的不相交路径 $P_1$ 和 $P_2$，$P_1 \geq P_2$，则 $P_1$ 是从根节点到叶节点的最长路径，$P_2$ 是其他所有和 $P_1$ 不相交的路径中最长的一条路径，此处的不相交指除了根节点之外的节点不相交
反证，设直径分解成的两条路径为 $P_1$ 和 $P_2$，且 $P_1 \geq P_2$，若存在一条从根节点到叶节点的路径 $P_3$ 满足 $P_3 > P_1$：
- 若 $P_1$ 和 $P_3$ 相交，则 $P_3$ 和 $P_2$ 不相交（因为树的性质，$P_1$ 这样的路径之间相交的第一个节点必然是根节点的其中一个子节点）那么 $P_3$ 和 $P_2$ 可以组成一条长度超过直径的链，矛盾
- 若 $P_1$ 和 $P_3$ 不相交，因为 $P_3 > P_1 \geq P_2$ ，则 $P_1$ 和 $P_3$ 可以组成一条长度超过直径的链，矛盾
所以 $P_1$ 是从根节点到叶节点的最长路径
若存在一条和 $P_1$ 不相交的路径 $P_3$ 满足 $P_2 < P_3$，则 $P_1$ 和 $P_3$ 可以组成一条长度超过直径的链，矛盾
所以 $P_2$ 是其他所有和 $P_1$ 不相交的路径中最长的一条路径
树的中心必然在树的直径的中间位置（一个或者两个）
假设树的中心在树的直径上，则显然会在中间位置。
假设不在树的直径上，设此时中心节点为 $N_0$，由树的性质：任意两个节点之间有且只有一条路径，可知 $N_0$ 到树的直径上的任意一点都存在一条路径，我们选择最短的那一条 $P_0$ 并假设其对应节点为 $N_1$ ，显然 $P_0$ 和直径只有 $N_0$ 这一个交点，不然就不是最短的了。此时由上面的那个性质可以知道以 $N_1$ 为根的树的高度是 $P_1$ 的长度（直径被 $N_1$ 分解为 $P_1$ 和 $P_2$）而以 $N_0$ 为根的树的高度至少是 $P_0 + P_1$ 的长度，那么这个时候 $N_0$ 已经不满足中心的定义了，矛盾
求树的直径和中心
大致上来讲有两种方法，1.两次DFS；2.树状DP
两次DFS
根据上一节推出的性质1可以很容易地证明这个方法是正确的。首先以任意节点为根，DFS找到最深的叶节点，然后以此叶节点为根，再次DFS找到最深的叶节点，这两个叶节点之间的路径就是树的直径，中心在这条路径的中间位置。
树状DP
求直径长
设我们以任意节点 $r$ 作为根，对于树中的每一个节点 $u$, 我们记录以 $u$ 为根的子树中从根到叶节点的最长的两条不相交路径，设其长度分别为 $d_1[u]$ 和 $d_2[u]$, 并令 $d_1 \geq d_2$. 那么显然 $d_1 + d_2$ 最大的节点都是直径上的节点 (逆命题不一定成立)，并且 $\max(d_1 + d_2)$ 就是直径长，那么可以采用树状DP的做法来计算每个节点的 $d_1$ 和 $d_2$.
求中心
因为在上面的求直径长的做法中存在对于一个直径上的节点 $u$，其父节点也是直径上的节点的情况，这个时候还要计算上包含其父节点的最长路径长度 $up[u]$ , 然后才能计算中心 $c = \underset{u}{\min}\max(d_1[u], up[u])$.
为了确保 $up$ 和 $d_1, d_2$ 也不相交，对于 $u$ 的父节点 $f$, 如果 $f$ 的 $d_1$ 对应的那条路径上第一个节点就是 $u$ 的话，则 $up[u] = \max(up[f], d_2[f])$, 不然的话就是 $up[u] = \max(up[f], d_1[f])$.
// link: https://leetcode-cn.com/problems/minimum-height-trees/
class Solution {
private:
void search_below(int root, int father,
vector<int> & d1, vector<int> & d2,
vector<int> & n1, vector<int> & n2,
const vector<vector<int>> & E) {
for (auto t : E[root]) {
if (t == father) continue;
search_below(t, root, d1, d2, n1, n2, E);
// 这样的更新规则确保d1, d2不相交
if (d1[t] + 1 > d1[root]) {
d2[root] = d1[root];
n2[root] = n1[root];
d1[root] = d1[t] + 1;
n1[root] = t;
}
else if (d1[t] + 1 > d2[root]) {
d2[root] = d1[t] + 1;
n2[root] = t;
}
}
}
int search_above(int root, int father,
vector<int> & d1, vector<int> & d2,
vector<int> & n1, vector<int> & up,
vector<int> & max_lens, const vector<vector<int>> & E) {
if (father != -1) {
if (n1[father] != root) up[root] = max(d1[father], up[father]) + 1;
else up[root] = max(d2[father], up[father]) + 1;
}
int min_len = max(d1[root], up[root]);
max_lens[root] = min_len;
for (auto t : E[root]) {
if (t == father) continue;
min_len = min(min_len, search_above(t, root, d1, d2, n1, up, max_lens, E));
}
return min_len;
}
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
// build edges
vector<vector<int>> E(n, vector<int>());
for (const vector<int> &e : edges) {
E[e[0]].push_back(e[1]);
E[e[1]].push_back(e[0]);
}
// DP buffers
// d1[i]: max depth from node i to leafs in subtree whose root is i.
// d2[i]: second max depth ...(same as above)
// up[i]: max length of chain from node i to leafs "above" i.
// n1[i]: subtree's root of i. This subtree contains max depth path from i to leaf.
// n2[i]: same as above, the second max depth path. Also reused as result buffer.
vector<int> d1(n, 0), d2(n, 0), up(n, 0), n1(n, -1), n2(n, -1);//, max_lens(n, 0);
search_below(0, -1, d1, d2, n1, n2, E);
int min_len = search_above(0, -1, d1, d2, n1, up, n2, E);
vector<int> ans;
for (int i = 0; i < n; ++i)
if (n2[i] == min_len) ans.push_back(i);
return ans;
}
};