Q:

Diameter of a tree graph

I'm asking myself what's wrong with my code to find the diameter of a tree:
(By diameter of a tree, I mean the greatest distance between two nodes in that tree graph)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1000005
int n,a,b;
int dist[MAXN];
vector<int> adj[MAXN];
vector<int> ways;
void dfs(int U, int father){
    if(father==U){
        dist[U]=1;
    }
    else{
        dist[U]=1+dist[father];
    }
    for(int i=0;i<(int)adj[U].size();i++){
        int V=adj[U][i];
        if(dist[V]==-1) dfs(V,U);
    }
}
void solve(int S){
    dist[S]=0;
    for(int j=0;j<(int)adj[S].size();j++){
        int w=adj[S][j];
        dfs(w,w);
        int maxdist=0;
        for(int i=1;i<=n;i++){
            if(dist[i]!=-1){
                maxdist=max(maxdist,dist[i]);
                dist[i]=0;
            }
        }
        ways.push_back(-maxdist);
    }
}
int main(){
    cin>>n;
    if(n==2) cout<<"1\n";
    else{
    for(int i=1;i<=n;i++){
      dist[i]=-1;
    }
    for(int i=1;i<n;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int vert;
    for(int i=1;i<=n;i++){
        if((int)adj[i].size()>1){
            vert=i;
            break;
        }
    }
    solve(vert);
    sort(ways.begin(),ways.end());
    int ret=-(ways[0]+ways[1]);
    cout<<ret<<"\n";
    }
    return 0;
}

For me, it sounds logical and very procedural, but I submitted it to an online judge and it was not accepted. What's going on?

A:

You measure the distance between two nodes in a tree by A and B.
distanceBetwwen_A_and_B = Distance A -> CommonAncestor(A, B)
                        + Distance B -> CommonAncestor(A, B);

So for a given Ancestor Node G it has a maximum radius of:
Diameter(G)   = Distance_To_Furthest_Child(G->left)
              + Distance_To_Furthest_Child(G->right)

But one of its descendants may have a larger radius than it has itself.
Max_Diameter(G) = max(Diameter(G), Max_Diameter(G->left), Max_Diameter(G->right))

From this you should be able to depth first search and a single traversal to calculate the Max_Diameter(Root)
struct Node
{
    Node*  l;
    Node*  r;
    int    maxD;
};

int findMaxD(Node* root)
{
    if (root == nullptr) {
        return 0;
    }
    calcMaxDiameter(root);
    return root->maxD;
}
/*
 * Sets the maxD value of a node
 * Returns the distance to the furthest decendant
 */
int calcMaxDiameter(Node* root)
{
    // If we fall of the end
    // The distance is zero.
    if (root == nullptr) {
        return 0;
    }
    int l_Distance = calcMaxDiameter(root->l);
    int r_Distance = calcMaxDiameter(root->r);

    // Calculate the preliminary Radius.
    root->maxD = l_Distance + r_Distance;
    if (root->l) {
        // If there is a left node see if it is bigger
        // than the current radius
        root->maxD = std::max(root->maxD, root->l->maxD);
    }
    if (root->r) {
        // If there is a right node....
        root->maxD = std::max(root->maxD, root->r->maxD);
    }
    // Return the distance to the furthest
    // ancestor. Add one for the distance from here
    // to the parent.
    return std::max(l_Distance, r_Distance) + 1;
}
    

