网站设计模板免费建站,网站做支付,洛阳市建设监理协会网站,农场游戏系统开发网站建设推广牛客题霸 [ 树的直径] C题解/答案
题目描述
给定一棵树#xff0c;求出这棵树的直径#xff0c;即两个节点距离的最大值。
题解#xff1a;
不知道大家听没听过一个结论#xff1a; 树的直径可以通过两边dfs找到 步骤#xff1a; 1.从任意一点进行dfs#xff0c;然后…牛客题霸 [ 树的直径] C题解/答案
题目描述
给定一棵树求出这棵树的直径即两个节点距离的最大值。
题解
不知道大家听没听过一个结论 树的直径可以通过两边dfs找到 步骤 1.从任意一点进行dfs然后找到一个最长路径记录最远点u 2.然后从u再进行dfs找最长路径记录一点v。 uv就是树的直径 证明 我们可以看出图中树的直径是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;vectorvectorpairint,int G;void dfs(int u,int deep,int fa){if(deepMax){faru;Maxdeep;}for(auto it:G[u]){int vit.first;int wit.second;if(vfa)continue;dfs(v,deepw,u);}}int solve(int n, vectorInterval Tree_edge, vectorint Edge_value) {// write code hereG.clear(); G.resize(n 1);for (int i 0; i n - 1; i) {Interval e Tree_edge[i];int w Edge_value[i];int ue.start;int ve.end;G[u].push_back(pairint,int(v, w));G[v].push_back(pairint,int(u, w));}far 1; Max 0;dfs(1, 0, 0);dfs(far, 0, far);return Max;}
};
