树的直径

发表于 | 分类于 | 浏览
字数统计: 551 | 阅读时长 ≈ 2

定义

 定义一颗树上最远两个叶子结点的距离为树的直径。

求解

 很容易想到一个$O(n^2)$的暴力算法，即遍历所有的叶子结点，找到距离最远的那两个，距离即为所求，但是复杂度过高，对于$n \geq 1e5$的情况便会显得力不从心。

 现在给出$O(n)$算法步骤：

  1. 以任意节点为根（以下称该点为$root$），找到距离该节点最远的叶子结点$x$；
  2. 以叶子节点$x$为根节点，找到距离该节点最远的叶子结点$y$；
  3. $dis(x,y)$即为所求；

证明

 假设$dis(x,y)$不为最大值，那么必然存在叶子结点$x,y$使得$dis(x’,y’)>dis(x,y)$，通过以下步骤，可证明$x’=x,y’=y$。

  1. 路径$x \to y$一定会经过$x \to root$上的部分节点，否则与$x$为距离$root$的最远叶子结点的前提相违背；

  2. 设$x \to y$与$x \to root$的分叉节点为$z$，即$x \to z \to y$，$x \to z \to root$，那么显然有$dis(z,x) \geq dis(z,y)$；

  3. 由于树上任意两节点联通，设$x’ \to y’$与$root$的联通节点为$z’$，由于$x \to y$是所有与节点中与$x$距离最远的，所以显然有$dis(z,y)\geq dis(z,y’) \geq dis(z’,y’)$，同理有$dis(z,y)\geq dis(z,x’) \geq dis(z’,x’)$，，那么$x’,y’$中必有一点等于$y$，否则将会产生一条新的最长链大于$dis(x’,y’)$；
  4. 假设$y’=y$，现在只需证明$x’=x$即可，又因为$2$中以证明$dis(z,x) \geq dis(z,y)$，且根据$3$中$dis(z,y)\geq dis(z,y’) \geq dis(z’,y’)$，$x’=x$是显然的，理由同$3$。
证毕

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
const int maxn = 2e6 + 10;
int dis[maxn], Max = 0;
vector<int> v[maxn];
void dfs(int u, int fa) {
    int len = v[u].size();
    if(len == 1 && dis[u] > dis[Max]) Max = u; 
    for(int i = 0; i < len; ++i) {
        if(v[u][i] == fa) continue;
        dis[v[u][i]] = dis[u] + 1;
        dfs(v[u][i], u);
    }
}
int main() {
    //read data before...
    dfs(1);
    dis[Max] = 0;
    dfs(Max);
    cout << dis[Max] << '\n';
    return 0;
}