求树的直径

欢迎来踩本人博客
树的直径：
就是树上最长路
方法 ：
求两边DFS即可

步骤：
1.从任意一点进行dfs，然后找到一个最长路径，记录最远点u
2.然后从u再进行dfs，找最长路径，记录一点v。
（u，v）就是树的直径

证明：可以看这个视频的第27：00（求树直径的原理和证明）

[video(video-iMl9BSet-1586583241905)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=95472415)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/5424cdb28ca513d905dc860808d8ea69fa389d1e.jpg)(title-第四届蓝桥杯a组)]

证明：

我们可以看出图中，树的直径是（4->2->5），长度为9.
我们一开始选定一个点dfs
如果是直径外一点，比如w1，从w1进行dfs找到的就是点4，路径就1->2->4，这个路径一定会与树的直径相交，而找到的4是直径的一端，那从4再进行dfs就是树的直径的另一端5，这样两遍dfs你就找到了树的直径
如果是直径内一点，比如w2，从w2开始dfs找到的最远点4，这个路径会被包含在树的直径里，那找到的点也就是树直径的一端，再dfs就可以找到另一端。
综上用两遍dfs就可以找到树的直径

代码：

网上找的模板：

#include <bits/stdc++.h>
using namespace std;


#define INF 10000000000

vector <int > G[1000005];
vector<int > E[1000005];
bool vis[1000005];
int d[1000005];

void init() {
    memset(vis, 0, sizeof(vis));
} 

void dfs(int u) {
    vis[u] = 1;
    int size = G[u].size();        //与顶点u相连的点数 

    for (int i = 0; i<size; i++) {            //对与顶点u相连的点数进行扫描 
        int v = G[u][i];
        if (!vis[v]) {
            d[v] = d[u] + E[u][i];
            dfs(v);
        }
    }
}

int main() {
    int n;
    cin >> n;
    int u, v, w;
    for (int i = 0; i<n-1; i++) {        //建立树过程 
        scanf("%d%d%d",&u,&v,&w);
        G[u-1].push_back(v-1);                //顶点两边都要记录 
        E[u-1].push_back(w);
        G[v-1].push_back(u-1);
        E[v-1].push_back(w);
    }

    init();
    for (int i = 0; i<n; i++)    d[i] = (i == 0?0:INF);
    dfs(0);
    int start = 0;
    int max = -1;
    for (int i = 0; i<n; i++) {
        if (d[i] > max && d[i] != INF) {
            max = d[i];
            start = i;
        }
    }

    init();
    for (int i = 0; i<n; i++)    d[i] = (i == start?0:INF);
    dfs(start);
    int ans = -1;
    for (int i = 0; i<n; i++) {
        if (d[i] > ans && d[i] != INF) {
            ans = d[i];
        }
    }

    //ans = 10*ans + ans*(ans+1)/2;
    cout << ans << endl;                    //ans  即为直径 
    return 0;
}