Cod sursa(job #2900557)

Utilizator disinfoion ion disinfo Data 11 mai 2022 10:17:21
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#define MAX 100010
using namespace std;

vector<int> children[MAX];
int parent[MAX];
int d[MAX];
int diam[MAX];
int root = 1;

void init_distances(int node){
	int ans = -1;
	for(auto x:children[node]){
		init_distances(x);
		ans = max(ans, d[x]);
	}

	d[node] = ans + 1;
}

void compute_diams(int node){
	if(d[node] == 0)
		return;
	else{
		int max1 = -1;
		int max2 = -1;
		int child1, child2;
		int max_diam = 0;
		for(auto x:children[node]){
			compute_diams(x);
			max_diam = max(diam[x], max_diam);

			if(d[x] >= max1){
				child2 = child1;
				child1 = x;
				max1 = d[child1];
				max2 = d[child2];
			}
			else if(d[x] >= max2){
				child2 = x;
				max2 = d[child2];
			}
		}

		if(children[node].size() >= 2)
			max_diam = max(2 + max1 + max2, max_diam);

		diam[node] = max_diam;	
	}
}

int main(){
	ifstream fin;
	ofstream fout;
	fin.open("darb.in");
	fout.open("darb.out"); 
	int m, n, q, a, b;
	fin >> n;

	for(int i=1; i <= n - 1; ++i){
		fin >> a >> b;
		children[a].push_back(b);
		parent[b] = a;
	}

	while(parent[root] != 0)
		root = parent[root];

	init_distances(root);
	compute_diams(root);

	// for(int i=1; i <= n; ++i){
	// 	fout << i << ": " << diam[i] << ", ";
	// }
	fout << diam[root] + 1;

}