以下方法是否正确找到 "Longest Path In a Tree"？

Question

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

}

这种方法正确吗？

Answer 1

是的，没错。证明思路如下。设 u 和 v 为树直径的端点。设 w 为 u 和 v 的最低共同祖先。如果它是 u（或 v），则最远的叶子正好是另一个顶点。因此，您的解决方案在检查具有一个 child 的顶点时会考虑到它。否则，到w的不同子树中最远的两个叶子的距离恰好是到v和u的距离（否则不是直径）。因此，当您的解决方案检查具有 2 个或更多 children 的任何顶点的两个最远的叶子时，它会被考虑在内。

以下方法是否正确找到 "Longest Path In a Tree"？

Is the following approach correct to find "Longest Path In a Tree"?

algorithm

data-structures

graph

tree

theory