Cod sursa(job #1911305)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 20:04:02
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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;
	}
}

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

	for (const auto& fiu : g[nod]) {
		if (fiu == tata)
			continue;
		dfs(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;
}
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);
	}

	dfs(1, 0);
	cout << max(dp[1][0], dp[1][1]);
}