Cod sursa(job #1911316)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 20:06:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 1e5 + 2;

int n, dp[nMax][2];
vector<int>g[nMax];

void add_edge(int a, int b) {
	g[a].push_back(b);
	g[b].push_back(a);
}

void upd(pair<int, int>&that, int value) {
	if (value > that.first) {
		that.second = that.first;
		that.first = value;
	}
	else if (value > that.second) {
		that.second = value;
	}
}

int diam(int nod, int tata) {
	int res = 0;
	dp[nod][0] = 1;
	pair<int, int>best(0, 0);

	for (const auto& fiu : g[nod]) {
		if (fiu == tata)
			continue;

		res = max(res, diam(fiu, nod));
		upd(best, dp[fiu][0]);
		dp[nod][0] = max(dp[nod][0], dp[fiu][0] + 1);
	}

	dp[nod][1] = best.first + best.second + 1;
	res = max(res, dp[nod][0]);
	res = max(res, dp[nod][1]);
	return res;
}
int main() {
	ifstream cin("darb.in");
	ofstream cout("darb.out");

	cin >> n;

	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		add_edge(x, y);
	}

	cout << diam(1, 0);
	return 0;
}