1021. Deepest Root (25)

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int n;
int a[10001][10001];
int mark[10001];
int components = 0;
int maxLevel = 0;
vector<int> elements;
void dfs(int root, int i, int level) {
	if (level > maxLevel) {
		maxLevel = level;
		elements.clear();
		elements.push_back(root);
	}
	else if (level == maxLevel) {
		if (root != elements[elements.size() - 1])
			elements.push_back(root);
	}
	for (int j = 1; j <= n; j++) {
		if (a[j][i] > 0 && j != i&&mark[j] == 0) {
			mark[j] = 1;
			dfs(root, j, level + 1);
		}
	}
}
void CalcComp(int p) {
	for (int i = 1; i <= n; i++) {
		if (a[p][i] > 0 && p != i&&mark[i] == 0) {
			mark[i] = 1;
			CalcComp(i);
		}
	}
}
int main(void) {
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		a[u][v] = 1;
		a[v][u] = 1;
	}
	while (true)
	{
		int p, cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (mark[i] == 0) {
				components++;
				mark[i]++;
				p = i;
				break;
			}
			else {
				cnt++;
			}
		}
		if (cnt == n) {
			cnt = 0;
			break;
		}
		CalcComp(p);
	}
	if (components > 1) {
		cout << "Error: " << components << " components";
		return 0;
	}
	if (n <= 15) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				mark[j] = 0;
			mark[i] = 1;
			dfs(i, i, 1);
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				cnt += a[i][j];
			}
			if (cnt == 1)
				elements.push_back(i);
			cnt = 0;
		}
	}
	for (int i = 0; i < elements.size(); i++) {
		cout << elements[i] << endl;
	}
	return 0;
}