猫史档案馆

【直击OI】【C++】基础树上问题——树的直径

 

 

概念

树中所有最短路径距离的最大值即为树的直径。

 

举个栗子，树（假定每条边的权值都是1）

1

/  \

2     3

的最长路径就是

2-1-3

所以它的直径就是2.

 

错误示范

 

请尽量反其道而行之。

 

A：多源最短路？跑一跑floyd不就行了？这么简单！

真是秉承了喵出奇迹的精神……

扑街*1

 

B：树上每个点对都求一遍LCA不就得了？这么简单！

您太客气了……

扑街*2

 

算法解析

 

喵算法，O(n^2)，太巨（雾

 

论记忆化搜索与动态规划

实际上dp就是一种按简单循环规律的记忆化搜索，每次记录答案，两种算法的复杂度是相同的。

 

经典算法1：树形dp

考虑一棵树的直径与其根的关系，它要么经过根，要么完全在根的一个子树里。

如果直径经过根，考虑根将直径分成的两个部分，它们是子树中从根向下的最长的两条路径。(最长和次长)

对于直径不经过根（在根的一个子树内）的情况递归求解即可。

令f[i]为从i向下的最长路径长度，dfs过程中统计即可。

 

代码详解

 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100007;
vector<int> E[MAXN];
int n, ans;
int f(int x, int fa) {
    int m1 = 0, m2 = 0;            //最长和次长
    for (int i = 0; i < E[x].size(); ++i)
        if (E[x][i] != fa) {
            int r = f(E[x][i], x)+1;
            if (m1 < r) m2 = m1, m1 = r;
            else if (m2 < r) m2 = r;
        }
    if (ans < m1 + m2) ans = m1 + m2;
    return m1;
}
int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    f(1, -1);
    printf("%d\n", ans);
    return 0;
}

 

 

经典算法2：两遍dfs！

 

随便选一个点x，求出距离x最远的一个点y，然后再求出距离y最远的一个点z，yz一定是一条直径。

两遍dfs即可。

证明：关键是证明y一定是某一条直径的一个端点。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100007;
vector<int> E[MAXN];
int x,y,n,de[MAXN];
void f(int x, int fa) {
    de[x]=de[fa]+1;
    for (int i = 0; i < E[x].size(); ++i)
        if (E[x][i] != fa)
            f(E[x][i],x);
}
int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    f(1,0);x=1;
    for(int i=2;i<=n;i++)
        if(de[i]>de[x]) x=i;
    f(x,0);y=1;
    for(int i=2;i<=n;i++)
        if(de[i]>de[y]) y=i;
    cout<<de[y]-1;            //这里必须注意！因为y算了两次。
    return 0;
}

 

爵士精品，直击OI ！