Cod sursa(job #2481032)

Utilizator bogdanbenteaBentea Bogdan bogdanbentea Data 26 octombrie 2019 13:04:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

vector <int> v[100002];
int n,a,b,lant[100002],raspuns[100002],mx1,mx2;

void dfs(int curent, int parinte)
{
    lant[curent]=1;
    raspuns[curent]=1;
    int mx1,mx2,urm;
    mx1=0; mx2=0;
    for(int i=0;i<v[curent].size();i++)
    {
        urm=v[curent][i];
        if(urm != parinte)
        {
            dfs(urm,curent);
            lant[curent]=max(lant[curent],lant[urm]+1);
            raspuns[curent]=max(raspuns[curent],raspuns[urm]);

            if(lant[urm]>mx1)
            {
                mx2=mx1;
                mx1=lant[urm];
            }
            else if(lant[urm]>mx2)
            {
                mx2=lant[urm];
            }
        }
    }
    raspuns[curent]=max(raspuns[curent],mx1+mx2+1);
}


int main()
{
    fin>>n;
    for(int i=1;i<n;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,-1);
    fout<<raspuns[1];
    return 0;
}