Cod sursa(job #2892381)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 21 aprilie 2022 20:48:39
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

#define MAX_N 100000

using namespace std;

int depth[MAX_N], diam[MAX_N];
vector <int> edges[MAX_N];

void dfs( int u, int p ) {
    int max1, max2;

    max1 = max2 = 0;
    depth[u] = 1;
    for ( int v: edges[u] ) {
        if ( v != p ) {
            dfs( v, u );
            if ( depth[v] > max1 ) {
                max2 = max1;
                max1 = depth[v];
            }
            else if ( depth[v] > max2 )
                max2 = depth[v];
            diam[u] = max( diam[u], diam[v] );
            depth[u] = max( depth[u], depth[v] + 1 );
        }
    }
    diam[u] = max( diam[u], max1 + max2 + 1 );
}

int main() {
    ifstream cin( "darb.in" );
    ofstream cout( "darb.out" );

    int n, u, v, i;

    cin >> n;
    for ( i = 0; i < n - 1; i++ ) {
        cin >> u >> v;
        u--;
        v--;

        edges[u].push_back( v );
        edges[v].push_back( u );
    }

    dfs( 0, -1 );

    cout << diam[0];

    return 0;
}