下面的方法是否正确找到“树中最长的路径”？

在问题中，我们必须找到树中最长的路径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; 

}

该方法是否正确？

来源

2016-12-16 Patel Parth

它通过了所有的测试例子吗？ – MrSmith42

是的。据judje接受。 –

交叉发表：http://cs.stackexchange.com/q/67524/755，http://stackoverflow.com/q/41188025/781723。请[不要在多个网站上发布相同的问题]（http://meta.stackexchange.com/q/64068）。每个社区都应该诚实地回答问题，不要浪费任何人的时间。 –

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

来源

2016-12-16 16:08:24 kraskevich

下面的方法是否正确找到“树中最长的路径”？

回答

相关问题