Cod sursa(job #3329505)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 13 decembrie 2025 15:59:47
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
vector <int> v[100005];
int max_diam;
int dfs( int x, int tata ){
	int i, y, a, max_sub1, max_sub2;
	max_sub1 = max_sub2 = 0;
	for( i = 0; i < v[x].size(); i++ ){
		y = v[x][i];
		if( y != tata ){
			a = dfs( y, x );
			//cout << x << ' ' << y << ' ' << a << '\n';
			if( a > max_sub1 ){
				max_sub2 = max_sub1;
				max_sub1 = a;
			}
			else if( a > max_sub2 ){
				max_sub2 = a;
			}
		}
	}
	max_diam = max( max_sub1 + max_sub2 + 1, max_diam );
	return max_sub1 + 1;
}
int main(){
	int n, i, x, y;
	ifstream fin( "darb.in" );
	ofstream fout( "darb.out" );
	fin >> n;
	for( i = 0; i < n - 1; i++ ){
		fin >> x >> y;
		v[x].push_back( y );
		v[y].push_back( x );
	}
	dfs( 1, 0 );
	fout << max_diam;
	return 0;
}