Cod sursa(job #3212456)

Utilizator lazureanrLazurean Razvan lazureanr Data 11 martie 2024 19:13:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

const int Nmax=100005;

vector<int> L[Nmax];

int n,sol,maxLen[Nmax];

void dfs(int node,int father)
{
    int max1=0,max2=0;
    for(int son:L[node])
    {
        if(son!=father)
        {
            dfs(son,node);
            if(maxLen[son]>max1)
            {
                max2=max1;
                max1=maxLen[son];
            }
            else
            {
                if(maxLen[son]>max2)
                {
                    max2=maxLen[son];
                }
            }
        }
    }
    sol=max(sol,max1+max2+1);
    maxLen[node]=max1+1;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs(1,0);
    fout<<sol;
    return 0;
}