Cod sursa(job #2030086)

Utilizator amaliarebAmalia Rebegea amaliareb Data 1 octombrie 2017 02:19:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>
#include <algorithm>
#define ll long long

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n,i,j,x,y,viz[100005],distmax[100005],sol=0;
vector<int> v[100005];

void dfs(int nod)
{
    int i, fiu, dist=0, maxi1=0, maxi2=0;
    for(i=0;i<v[nod].size();i++)
    {
        fiu=v[nod][i];
        if(!viz[fiu])
        {
            viz[fiu]=1;
            dfs(fiu);
            dist=max(dist,distmax[fiu]);
            if(distmax[fiu]>maxi1) maxi2=maxi1, maxi1=distmax[fiu];
            else if(distmax[fiu]>maxi2) maxi2=distmax[fiu];
        }
    }
    distmax[nod]=dist+1;
    if(maxi1 && maxi2) sol=max(sol,maxi1+maxi2+1);
}

int main()
{
    f>>n;
    for(i=1;i<n;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    viz[1]=1;
    dfs(1);
    for(i=1;i<=n;i++) if(distmax[i]>sol) sol=distmax[i];
    g<<sol<<'\n';
    return 0;
}