Cod sursa(job #2329731)

Utilizator netfreeAndrei Muntean netfree Data 27 ianuarie 2019 13:05:09
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const string NAME = "darb";

ifstream fin(NAME+".in");
ofstream fout(NAME + ".out");

const int N_MAX = 100000 + 5;

vector<int> vec[N_MAX];
int viz[N_MAX];

int n;

bool cmp(int a, int b){
    return (a>b);
}

int darb(int nod){
    viz[nod] = true;
    if(nod != 1){
        int maxx = 0;
        for(auto v : vec[nod])
            if(!viz[v])
                maxx = max(maxx, darb(v));
        return maxx + 1;
    } else
    {
        vector<int> ans;
        for(auto v : vec[nod])
            if(!viz[v])
                ans.push_back(darb(v));
        sort(ans.begin(), ans.end(), cmp);
        if(ans.size() >= 2)
            return ans[0] + ans[1] + 1;
        else if(ans.size() == 1)
            return ans[0] + 1;
        else return 1;
    }
}

int main()
{
    fin >> n;
    for(int i = 1, a, b; i<n; ++i){
        fin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    fout << darb(1);
    return 0;
}