Cod sursa(job #2481016)

Utilizator CojocaruVicentiuCojocaru Vicentiu CojocaruVicentiu Data 26 octombrie 2019 12:54:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> v[100010];
int lant[100010];
int raspuns[100010];
int n,i,a,b;
void dfs (int nod_curent, int parinte)
{
    int max1=0, max2=0,i;
    lant[nod_curent]=1;
    raspuns[nod_curent]=1;
    for(i=0;i<v[nod_curent].size();i++)
    {
        int nod_urmator =v[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]>max1)
            {
                max2=max1;
                max1=lant[nod_urmator];
            }
            else
                if(lant[nod_urmator]>max2)
                    max2=lant[nod_urmator];
        }
    }
    raspuns[nod_curent]=max(raspuns[nod_curent],max1+max2+1);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,-1);
    fout<<raspuns[1];
    fin.close();
    fout.close();
    return 0;
}