Cod sursa(job #2795264)

Utilizator octavi26octavian octavi26 Data 6 noiembrie 2021 10:20:03
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define N 100008

using namespace std;

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

int n;
vector<int> A[N];
int maxLen[N];

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

int sol;

inline void Dfs(int nod, int last)
{
    int mx1, mx2;
    mx1 = mx2 = 0;
    for( auto fiu : A[nod] )
        if( fiu != last )
        {
            Dfs(fiu, nod);
            if( mx1 < maxLen[fiu] )
                mx2 = mx1, mx1 = maxLen[fiu];
            else if( maxLen[fiu] > mx2 )
                mx2 = maxLen[fiu];
        }
    maxLen[nod] = mx1 + 1;
    sol = max( sol, mx1 + mx2 + 1 );
}

void Rezolvare()
{
    Dfs(1, 0);
    fout << sol;
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}