Cod sursa(job #2481053)

Utilizator ralucaantonAnton Raluca ralucaanton Data 26 octombrie 2019 13:21:08
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector<int> vecini[100005];

int raspuns[100005],lant[1000005],n;

void dfs(int nod_curent, int parinte)
{
    int maxi1=0, maxi2=0;
    lant[nod_curent]=1;
    raspuns[nod_curent]=1;
    for(int i=0; i<vecini[nod_curent].size(); i++)
    {
        int nod_urmator = vecini[nod_curent][i];
        if(nod_urmator != parinte)
        {
            dfs(nod_urmator, nod_curent);
            lant[nod_curent] = max(lant[nod_curent], lant[nod_urmator]+1);
            raspuns[nod_curent] = max(raspuns[nod_curent], raspuns[nod_urmator]);

            if(lant[nod_urmator] > maxi1)
            {
                maxi2=maxi1;
                maxi1=lant[nod_urmator];
            }
            else
            {
                if(lant[nod_urmator]>maxi2)
                {
                    maxi2=lant[nod_urmator];
                }
            }
        }
    }
    raspuns[nod_curent]=max(raspuns[nod_curent], maxi1+maxi2+1);
}

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

    fin.close();
    fout.close();
    return 0;
}