Cod sursa(job #2481017)

Utilizator Turturica_DorinTurturica Dorin Turturica_Dorin Data 26 octombrie 2019 12:55:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>

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

vector< int > vecini[ 100005 ];

int lant[ 100005 ], raspuns[ 100005 ];

void dfs ( int nod_curent, int parinte )
{
    int m1 = 0, m2 = 0;
    lant[ nod_curent ] = 1;
    raspuns[ nod_curent ] = 1;
    for( int i = 0; i < vecini[ nod_curent ].size(); i++ )
    {
        int nod_urmator = vecini[ nod_curent ][ i ];
        if ( nod_urmator != parinte )
        {
            dfs( nod_urmator, nod_curent );
            lant[ nod_curent ] = max( lant[ nod_curent ], lant[ nod_urmator ] + 1 );
            raspuns[ nod_curent ] = max( raspuns[ nod_curent ], raspuns[ nod_urmator ] );

            if ( lant[ nod_urmator ] > m1 )
            {
                m2 = m1;
                m1 = lant[ nod_urmator ];
            }
            else if ( lant[ nod_urmator ] > m2 )
            {
                m2 = lant[ nod_urmator ];
            }
        }
    }
    raspuns[ nod_curent ] = max( raspuns[ nod_curent ], m1 + m2 + 1 );
}

int main()
{
    int n, a, b;
    fin >> n;
    for ( int i = 1; i <= n; i++ )
    {
        fin >> a >> b;
        vecini[ a ].push_back( b );
        vecini[ b ].push_back( a );
    }
    dfs( 1, -1 );
    fout<< raspuns[ 1 ];
    fin.close();
    fout.close();
    return 0;
}