Cod sursa(job #2470017)

Utilizator RedXtreme45Catalin RedXtreme45 Data 8 octombrie 2019 16:57:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
vector <int> v[100001];
int c[100001];
int best;
void DFS(int x,int t)
{
    int max1=0,max2=0;
    for (vector <int>:: iterator it=v[x].begin();it!=v[x].end();++it)
    {
        int o=*it;
        if (o!=t)
        {
            DFS(o,x);
            if (c[o]>max1)
            {
                max2=max1;
                max1=c[o];
            }
            else if (c[o]>max2)
            {
                max2=c[o];
            }
        }
    }
    c[x]=max1+1;
    best=max(best,max1+max2+1);

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