Cod sursa(job #2533577)

Utilizator radustn92Radu Stancu radustn92 Data 29 ianuarie 2020 12:53:05
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
const int NMAX = 100505;

int N, bestDown[NMAX], parent[NMAX];
bool visited[NMAX];
vector<int> G[NMAX];

void read() {
	scanf("%d", &N);
	int x, y;
	for (int edgeIdx = 0; edgeIdx < N - 1; edgeIdx++) {
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

int dfs(int node) {
	visited[node] = true;
	int result = 0;

	for (auto& neighbour : G[node]) {
		if (!visited[neighbour]) {
			parent[neighbour] = node;
			result = max(result, dfs(neighbour));
		}
	}

	vector<int> childCandidates;
	for (auto& neighbour : G[node]) {
		if (parent[neighbour] == node) {
			childCandidates.push_back(bestDown[neighbour]);
		}
	}

	if (childCandidates.size() >= 2) {
		nth_element(childCandidates.begin(), childCandidates.begin() + 2, childCandidates.end(), greater<int>());
	}

	bestDown[node] = 1 + (!childCandidates.empty() ? childCandidates[0] : 0);
	result = max(result, bestDown[node]);
	if (childCandidates.size() >= 2) {
		result = max(result, 1 + childCandidates[0] + childCandidates[1]);
	}

	return result;
}

int main() {
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);

	read();
	printf("%d\n", dfs(1));
	return 0;
}