Cod sursa(job #2217280)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 29 iunie 2018 20:44:03
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

const int N=100000;
int n,root;
vector<int>v[N+5];
int in[N+5];
int cnt[N+5];

void dfs(int nod) {
    int ma=0;
    for(auto nou:v[nod]) {
        dfs(nou);
        ma=max(ma,cnt[nou]);
    }
    cnt[nod]=ma+1;
}

int ans=0;

vector<int>len;

int main() {
    fin>>n;
    for(int i=1;i<n;i++) {
        int a,b;
        fin>>a>>b;
        v[a].push_back(b);
        in[b]++;
    }
    for(int i=1;i<=n;i++) {
        if(in[i]==0) {
            root=i;
        }
    }
    dfs(root);
    ans=cnt[root];
    while(v[root].size()==1)
        root=v[root][0];
    if(v[root].size()>=2) {
        for(auto nod:v[root]) {
            dfs(nod);
            len.push_back(cnt[nod]);
        }
        sort(len.rbegin(),len.rend());
        ans=max(ans,len[0]+len[1]+1);
    }
    fout<<ans<<"\n";
    return 0;
}