Cod sursa(job #2468364)

Utilizator BaraianTudorBaraian Tudor Stefan BaraianTudor Data 5 octombrie 2019 14:34:24
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#define pb push_back
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int n,x,y,best;
vector <int> v[100005];
int maxim[100005];
void dfs(int nod,int t)
{
    int maxim1=0,maxim2=0;
    for(auto i:v[nod])
    {
        if(i!=t)
        {
            dfs(i,nod);
            if(maxim[i]+1>maxim1)
            {
                maxim2=maxim1;
                maxim1=maxim[i];
            }
            else if(maxim[i]+1>maxim2)
            {
                maxim2=maxim[i];
            }
        }
    }
    maxim[nod]=maxim1+1;
    best=max(best,maxim1+maxim2+1);
}
int main()
{
    in>>n;
    for(int i=1;i<=n-1;i++)
    {
        in>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(2,0);
    out<<best;
    return 0;
}