### 思路
1. 使用DFS遍历树,计算每个节点的子树大小。
2. 计算每个节点的最大连通块大小。
3. 找到最大连通块大小最小的节点,即为树的重心。
### 伪代码
1. 读取输入数据,构建树的邻接表。
2. 定义DFS函数,计算每个节点的子树大小。
3. 遍历所有节点,计算每个节点的最大连通块大小。
4. 找到最大连通块大小最小的节点,输出结果。
### C++代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100000 + 5;
vector<int> adj[MAXN];
int subtree_size[MAXN];
int max_subtree[MAXN];
int n;
void dfs(int u, int parent) {
subtree_size[u] = 1;
max_subtree[u] = 0;
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
subtree_size[u] += subtree_size[v];
max_subtree[u] = max(max_subtree[u], subtree_size[v]);
}
max_subtree[u] = max(max_subtree[u], n - subtree_size[u]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, -1);
int min_max_subtree = n;
vector<int> centroids;
for (int i = 1; i <= n; ++i) {
if (max_subtree[i] < min_max_subtree) {
min_max_subtree = max_subtree[i];
centroids.clear();
centroids.push_back(i);
} else if (max_subtree[i] == min_max_subtree) {
centroids.push_back(i);
}
}
sort(centroids.begin(), centroids.end());
for (int centroid : centroids) {
printf("%d ", centroid);
}
printf("\n");
return 0;
}
### 细节
1. 使用邻接表存储树的结构。
2. 使用DFS计算每个节点的子树大小和最大连通块大小。
3. 遍历所有节点,找到最大连通块大小最小的节点。
4. 输出结果时,若有多个重心,按节点编号从小到大输出。