Cod sursa(job #2196467)

Utilizator sergiudnyTritean Sergiu sergiudny Data 19 aprilie 2018 13:29:10
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>
#define DM 100005
#define pb push_back
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

bitset<DM>viz;
vector<int>v[DM];
int n,x,y,dist[DM],mx;

void dfs(int nod){
    viz[nod]=1;
    int mx1=0,mx2=0;
    for(auto i:v[nod]){
        if(!viz[i]) dfs(i);
        if(mx1<dist[i]) mx2=mx1,mx1=dist[i];
        else if(mx2<dist[i]) mx2=dist[i];
    }
    dist[nod]=mx1+1;
    if(mx1 && mx2) mx=max(mx,mx1+mx2+1);
}

int main()
{
    fin>>n;
    for(int i=1;i<n;++i){
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1);
    fout<<mx;
    return 0;
}