牛客题霸 [ 树的直径] C++题解/答案

题目描述

给定一棵树,求出这棵树的直径,即两个节点距离的最大值。

题解:

不知道大家听没听过一个结论:
树的直径可以通过两边dfs找到
步骤:
1.从任意一点进行dfs,然后找到一个最长路径,记录最远点u
2.然后从u再进行dfs,找最长路径,记录一点v。
(u,v)就是树的直径
证明:

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


其实求直径也就是求深度,所以我们dfs直接求树的深度,并记录最大深度,以及对应的节点,然后再带入到第二遍dfs即可

代码:

/** * struct Interval { * int start; * int end; * }; */

class Solution {
   
public:
    /** * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类vector 树的边 * @param Edge_value int整型vector 边的权值 * @return int整型 */int far,Max;
    vector<vector<pair<int,int> >>G;
    void dfs(int u,int deep,int fa)
    {
   
        if(deep>Max)
        {
   
            far=u;
            Max=deep;
        }
        for(auto &it:G[u])
        {
   
            int v=it.first;
            int w=it.second;
            if(v==fa)continue;
            dfs(v,deep+w,u);
        }
    }
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
   
        // write code here
        G.clear(); 
        G.resize(n + 1);
        for (int i = 0; i < n - 1; ++i) {
   
            Interval e = Tree_edge[i];
            int w = Edge_value[i];
            int u=e.start;
            int v=e.end;
            G[u].push_back(pair<int,int>(v, w));
            G[v].push_back(pair<int,int>(u, w));
        }
        far = 1; Max = 0;
        dfs(1, 0, 0);
        dfs(far, 0, far);
        return Max;
    }
};