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

Question

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?

Answer 1

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.