Cod sursa(job #2501195)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 29 noiembrie 2019 11:00:38
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
vector < int > L[100009];
int n, i, sol, x, y;
int fr[100009], d[100009];

void dfs ( int nod ){
    fr[nod] = 1;
    d[nod] = 1;
    int maxi1 = -1, maxi2 = -1;
    for ( int i=0; i < L[nod].size(); i++ ){
        int vecin = L[nod][i];
        if ( !fr[vecin] ){
            dfs ( vecin );
            d[nod] += d[vecin];
            if ( d[vecin] >= maxi1 ){
                maxi2 = maxi1;
                maxi1 = d[vecin];
            } else if ( d[vecin] > maxi2 )
                        maxi2 = d[vecin];
        }
    }
    sol = max ( sol, maxi1+maxi2 );
}


int main()
{
    f>>n;
    for ( i=1; i < n; i++ ){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs(1);
    g<<sol;
    return 0;
}