本节介绍树的直径与重心的性质与求法。

树的直径

        给定一棵树，该树中最远的两点间距离称为该树的直径。有两种求解方法：

  • 两次搜索
            任选一点开始搜索，找到最大距离的点s，再从s开始搜索，找到最大距离的点t。s和t间距离就是树的直径。这种方法只适用与边权非负的情况，证明略。

  • 树型DP
            令dp[x]表示从x开始，向以x为根的子树上前进可以得到的最大距离。有状态转移方程：

            这里y是x的子结点，v是边权。
            这样并不能得出最终的结果，因为最长路有可能跨根结点，这时我们需要在DP过程中记录一下答案。注意到在更新dp[x]时（也就是在其下一个子结点之前），dp[x]已经记录了目前的最大长度，这时可以这样更新答案：

        这两种方法时间复杂度都是$O(n)$，但两次搜索版可以找到路径，DP版不易找。下面给出树型DP的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>

using namespace std;
struct Edge {
    int to, next, v;
} edge[20000];
int head[10000], n, cnt = 1, dp[10000], ans = -1;

inline void add(int x, int y, int z) {
    edge[cnt].v = z, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

int DP(int x, int fa) {
    dp[x] = 0;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (edge[i].to == fa)continue;//防止向父结点回溯
        ans = max(ans, dp[x] + DP(edge[i].to, x) + edge[i].v), dp[x] = max(dp[edge[i].to] + edge[i].v, dp[x]);
    }
    return dp[x];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    DP(1, 0);
    cout << ans << endl;
}

树的重心

        首先认识什么是重心。
        对于一棵无根树，我们需要选一个点作为根节点将其转化为有根树。如果以某一个点为根可以使得其最大的子树结点数最小，那么这个点称为树的重心。重心可以有多个。
        以重心为根可以得到尽可能平衡的有根树，下面是重心的其它性质：

  • 树中所有点到某个点的距离和中，到重心的距离和是最小的。有两个重心时，它们的距离和一样。
  • 把两个树通过一条边相连得到一个新的树，新的树的重心在连接原来两个树的重心的路径上。
  • 把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

        如何求重心呢？先随便选一点为根，然后用一遍DFS来在$O(n)$复杂度下求出每一个点的子树结点树和最大子树结点树，更新答案即可。下面用size记录子树结点数，f记录最大结点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>

using namespace std;
struct Edge {
    int to, next;
} edge[20000];
int head[10000], n, cnt = 1, size[10000], f[10000], ans = -1, minn = 0x7fffffff;

inline void add(int x, int y) {
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

void DFS(int x, int fa) {
    size[x] = 1, f[x] = 0;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (edge[i].to == fa)continue;
        DFS(edge[i].to, x), size[x] += size[edge[i].to], f[x] = max(f[x], size[edge[i].to]);
    }
    f[x] = max(f[x], n - size[x]);//注意！！还要考虑上面的树
    if (f[x] < minn)minn = f[x], ans = x;//更新答案，这里只求一个重心
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    DFS(1, 0);
    cout << ans << endl;
    return 0;
}