Cod sursa(job #2533573)

Utilizator radustn92Radu Stancu radustn92 Data 29 ianuarie 2020 12:46:18
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#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));
		}
	}

	int bestChildDown = -1, secondBestChildDown = -1;
	for (auto& neighbour : G[node]) {
		if (parent[neighbour] != node) {
			continue;
		}

		// improve 1st child
		if (bestChildDown == -1 || bestDown[bestChildDown] < bestDown[neighbour]) {
			secondBestChildDown = bestChildDown;
			bestChildDown = neighbour;
		} else if (secondBestChildDown == -1 || bestDown[secondBestChildDown] < bestDown[neighbour]) {
			secondBestChildDown = neighbour;
		}
	}

	bestDown[node] = 1 + (bestChildDown == -1 ? 0 : bestDown[bestChildDown]);
	result = max(result, bestDown[node]);
	if (bestChildDown != -1 && secondBestChildDown != -1) {
		result = max(result, 1 + bestDown[bestChildDown] + bestDown[secondBestChildDown]);
	}

	return result;
}

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

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