直径

发表于
CF 1045D

树上任意两节点之间最长的简单路径即为树的「直径」。

可以用两次 DFS 或者树形 DP 的方法在
O(n)O(n) 时间求出树的直径。

直接给出定理:在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
cosnt int N=1e5+10;
int n,c,d[N];
vector<int> E<N>;
void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

简单来说，是先任意找一端点，求出最长路径，那么找到的这个点一定是直径的一个端点，那么再做一次dfs就能找到另一个直径的端点。

求树上直径的点

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
int n, c = 0, t = 0, s = 0, mx = 0;
int d[N];
vector<int> e[N];
vector<int> path;

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) c = v;
        dfs1(v, u);
    }
}

bool dfs2(int u, int fa) { // 寻找 t，并把路径 push 回溯
    if (u == t) {
        path.push_back(u);
        return true;
    }
    for (auto v : e[u]) {
        if (v == fa) continue;
        if (dfs2(v, u)) {
            path.push_back(u);
            return true;
        }
    }
    return false;
}

树形dp

我们定义
dp[u]dp[u]：以
uu为根的子树中，从
uu 出发的最长路径。那么容易得出转移方程：
dp[u]=max⁡(dp[u],dp[v]+w(u,v))dp[u] = \max(dp[u], dp[v] + w(u, v))，其中的
v 为
u 的子节点，
w(u,v)w(u, 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
constexpr int N = 10000 + 10;

int n, d = 0;
int dp[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}
void solve(){
  cin >> n;
    clear_all();
    rep(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    s = c;  //第一个端点
    d[s] = 0;
    dfs1(s, 0);
    t = c;   // 另一个端点
    dfs2(s,0);
    //d[c]代表mx
}
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
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
vector<int>edge[100005];
int vis[100005];
int dis[100005];
void dfs(int st)
{
    for(int i=0;i<edge[st].size();i++)
    {
        int to=edge[st][i];
        if(!vis[to])
        {
            vis[to]=1;
            dis[to]=dis[st]+1;//注意，本代码计算的是无权树的直径，所以边权为1
            //如果是有权树，则这里的1要改为边权
            dfs(to);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;//n个点
    for(int i=1;i<=n-1;i++)//因为是树，有n-1条边
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);//无向图存储，若是有权树还要用结构体
    }
    dfs(1);//从1出发dfs一边
    int maxlen=0,Q,W,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]>maxlen) maxlen=dis[i],Q=i;
        dis[i]=vis[i]=0;
    }//找到直径的一个端点Q
    dfs(Q);//从Q出发
    for(int i=1;i<=n;i++)
        if(dis[i]>ans) ans=dis[i],W=i;//找到另一个端点W，同时得到直径长度
    return 0;
}