Cod sursa(job #1992395)

Utilizator lflorin29Florin Laiu lflorin29 Data 20 iunie 2017 13:34:58
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, down[N], up[N], dep[N];
vector <int> g[N];

void dfsdown(int nod, int father) {
	dep[nod] = dep[father] + 1;
	for (auto fiu : g[nod])
		if (fiu != father) {
			dfsdown(fiu, nod);
			down[nod] = max(down[nod], down[fiu] + 1);
		}
}

void dfsup(int nod, int father, int best) {
	if (father != 0) {
		up[nod] = dep[nod] + best;
	}
	int ind_best = 0, mx1 = 0, mx2 = 0;
	for (auto fiu : g[nod]) {
		if (fiu != father) {
			if (down[fiu] + 1 == down[nod]) {
				ind_best = fiu;
			}
			if (down[fiu] + 1 > mx1) {
				mx2 = mx1;
				mx1 = down[fiu] + 1;
			}
			else if (down[fiu] + 1 > mx2) {
				mx2 = down[fiu] + 1;
			}
		}
	}
	for (auto fiu : g[nod]) {
		if (fiu != father) {
			int upd = 0;
			if (fiu == ind_best) {
				upd = max(best, -dep[nod] + mx2);
			}
			else upd = max(best, -dep[nod] + mx1);
			dfsup(fiu, nod, upd);
		}
	}
}

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

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfsdown(1, 0);
	dfsup(1, 0, 0);
	int diam = 0;
	for(int i = 1; i <= n; ++i) {
        diam = max(diam, up[i]);
        diam = max(diam, down[i]);
	}
	cout << diam+1;
}