树的直径即树上一条最长的路径,显然其两端为叶子结点

两次dfs
第一次先任选一个节点u开始dfs,然后求出最远的点v
然后从v再做一次dfs,最后所求最长路径即为树的直径
复杂度 $O(n)$

证明:

  1. 若u为直径上的点,则显然v是直径的另一端。
  2. 若u不为直径上的点,则第一次dfs一定会与直径上的点相交,第一个相交的点到v一定是直径的一段。
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
struct Node
{
int d,p;
};

Node dfs(int u,int fa)
{
Node res = (Node){INF,-1};
bool leaf = true;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
leaf = false;
Node cur = dfs(v,u);
if(res.d < cur.d+1) res = (Node){cur.d+1,cur.p};
}
if(leaf) return (Node){0,u};
return res;
}

Node gao()
{
Node u = dfs(1,-1);
return dfs(u.p,-1);
}