Cod sursa(job #1916871)

Utilizator CraiuAndrei Craiu Craiu Data 9 martie 2017 10:33:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nMax = 100005;
int n, sol;
vector <int> L[nMax];
int dp[nMax];

inline void Citeste()
{
    int i, x, y;
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}

inline void Dfs(int nod, int tata)
{
    int max1 = 0, max2 = 0;
    for(auto it : L[nod])
    {
        if(it == tata) continue;
        Dfs(it, nod);
        if(max1 < dp[it])
        {
            max2 = max1;
            max1 = dp[it];
        }
        else if(max2 < dp[it])
            max2 = dp[it];
    }
    dp[nod] = max1 + 1;
    sol = max(sol, max1 + max2 + 1);
}

int main()
{
    Citeste();
    Dfs(1, 0);
    fout << sol << "\n";
    return 0;
}