以下方法是否正确找到“树中最长的路径”？(Is the following approach correct to find “Longest Path In a Tree”?)

在这个问题中，我们必须在树LINK中找到最长的路径。我的方法如下：我在树上运行dfs并计算每个顶点的深度并将该深度添加到该顶点的向量中。现在我们对所有顶点的向量进行排序。通过任何顶点的最长路径将包含该顶点将由dfs返回的两条不同的最长路径。请参阅以下代码以获得更多理解

#include<bits/stdc++.h> using namespace std; const int N=10000; vector<int> adjacencylist[N+1]; bool visited[N+1]={false}; vector<int> splitlist[N+1]; int dfs(int u) { visited[u]=true; int answer=0; for(int i : adjacencylist[u]) { if(!visited[i]) { int r=1+dfs(i); splitlist[u].push_back(r); answer=max(answer,r); } } return answer; } int main() { int nodes; cin >> nodes; for(int i=0;i<nodes-1;i++) { int u,v; cin >> u >> v; adjacencylist[u].push_back(v); adjacencylist[v].push_back(u); } dfs(1); for(int i=1;i<=nodes;i++) { sort(splitlist[i].begin(),splitlist[i].end(),greater<int>()); } int answer=0; for(int i=1;i<=nodes;i++) { if(splitlist[i].size()>1) answer=max(answer,splitlist[i].at(0)+splitlist[i].at(1)); else if(splitlist[i].size()==1) answer=max(answer,splitlist[i].at(0)); } cout << answer; }

这种方法是否正确？

In the problem we have to find longest path in a tree LINK. My approach is as below: I am running dfs on a tree and calculating the depth from every vertex and adding that depth to vector of that vertex. Now we sort the vectors of all vertex. And longest path through any vertex will contain two different longest path from that vertex which will be returned by dfs. See code below for more understanding.

#include<bits/stdc++.h> using namespace std; const int N=10000; vector<int> adjacencylist[N+1]; bool visited[N+1]={false}; vector<int> splitlist[N+1]; int dfs(int u) { visited[u]=true; int answer=0; for(int i : adjacencylist[u]) { if(!visited[i]) { int r=1+dfs(i); splitlist[u].push_back(r); answer=max(answer,r); } } return answer; } int main() { int nodes; cin >> nodes; for(int i=0;i<nodes-1;i++) { int u,v; cin >> u >> v; adjacencylist[u].push_back(v); adjacencylist[v].push_back(u); } dfs(1); for(int i=1;i<=nodes;i++) { sort(splitlist[i].begin(),splitlist[i].end(),greater<int>()); } int answer=0; for(int i=1;i<=nodes;i++) { if(splitlist[i].size()>1) answer=max(answer,splitlist[i].at(0)+splitlist[i].at(1)); else if(splitlist[i].size()==1) answer=max(answer,splitlist[i].at(0)); } cout << answer; }

Is this approach correct?

最满意答案

是的，这是正确的。证明的思想如下。设u和v是树直径的末端顶点。设w是u和v的最低共同祖先。如果它是u （或v ），那么最远的叶子就是另一个顶点。因此，您的解决方案在检查具有一个孩子的顶点时将其考虑在内。否则，到w不同子树中最远的两个叶子的距离就是到v和u的距离（否则，它不是直径）。所以当你解决方案检查两个或两个以上孩子的任何顶点的两个最远的叶子时，它会被考虑到。

Yes, it's correct. The idea of the proof is as follows. Let u and v be the end vertices of the diameter of the tree. Let w be the lowest common ancestor of u and v. If it's u (or v), the furthest leaf is exactly the other vertex. Thus, you solution takes it into account when it checks vertices with one child. Otherwise, the distance to the two furthest leaves in different subtrees of w is exactly the distance to v and u (otherwise, it's not a diameter). So it's taken into account when you solution checks two furthest leaves for any vertex with 2 or more children.

更多推荐