Cod sursa(job #1977301)

Utilizator retrogradLucian Bicsi retrograd Data 5 mai 2017 10:14:16
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 500000;

int Depth[kMaxN];
vector<int> G[kMaxN];

int DFSDown(int node, int par) {
	int ret = 0;
	if (par != -1) 
		G[node].erase(find(G[node].begin(), G[node].end(), par));
	
	for (auto vec : G[node])
		ret = max(ret, 1 + DFSDown(vec, node));
	
	Depth[node] = ret;
	return ret;
}

void DFSUp(int node, int up) {
	Depth[node] = max(Depth[node], up);

	++up;
	for (auto vec : G[node])
		up = max(up, Depth[vec] + 1);

	for (auto vec : G[node])
		DFSUp(vec, up);
}

int main() {
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
	
	int n;
	cin >> n;
	for (int i = 2; i <= n; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	DFSDown(1, -1);
	DFSUp(1, 0);

	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans = max(ans, Depth[i] + 1);
	cout << ans << endl;

	return 0;
}