树的重心是删除后使剩余连通块最大节点数最小的节点，可能有1或2个；通过一次DFS即可求得，因每个节点u的最大连通块大小为max(n−size[u], max{size[v]∣v为u的子节点})，只需在回溯时实时计算并判断是否≤n/2。
什么是树的重心，为什么dfs一遍就能找到
树的重心是删除后使剩余连通块最大 size 最小的那个节点（可能有 1 或 2 个）。关键性质是：以该点为根时，所有子树 size ≤ n/2，且其父方向“上方子树” size = n - size[u] 也必须 ≤ n/2。所以不需要枚举删点再 BFS，一次 DFS 就能算出每个点的子树大小和“向上部分”大小，进而判断是否满足重心条件。
怎么写标准的重心求解dfs
核心是两遍 DFS：第一遍求子树大小；第二遍换根，计算每个点作为根时的最大连通块 size。但实际可合并成一遍——在回溯时用子树 size 推出当前点的“最大连通块 size”，即：max( n - size[u], max(size[v] for v in children) )。
常见错误包括：
- 漏判父方向连通块：
n - size[u]必须参与比较 - 初始化
max_subtree为 0 而非 -1，否则无子节点时误判 - 把重心定义成“子树 size 最接近
n/2的点”，这是错的——必须保证所有连通块 ≤n/2
示例片段（邻接表存图，g 已建好）：
立即学习“C++免费学习笔记（深入）”；
int n;
vector<vector<int>> g;
vector<int> size, centroid;
void dfs(int u, int fa) {
size[u] = 1;
int max_subtree = 0;
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
size[u] += size[v];
max_subtree = max(max_subtree, size[v]);
}
max_subtree = max(max_subtree, n - size[u]);
if (max_subtree <= n / 2) centroid.push_back(u);
}
多个重心怎么处理，vector<int></int> 还是只取一个
一棵树最多有两个重心，且一定相邻。如果你只需要任一重心（比如做点分治的根），取 centroid[0] 即可；如果需全部，保留整个 centroid vector。注意：当 n 为偶数且存在两个重心时，它们分割出的各连通块 size 都等于 n/2，此时 max_subtree == n/2，仍满足 ≤ n/2 条件，不会被漏掉。
性能上无差异，但逻辑上必须允许重复收集——不能遇到第一个就 return。
输入是无向边，建图时要不要加双向边
要。树是无向图，g[u].push_back(v) 和 g[v].push_back(u) 都必须有。否则 DFS 会漏掉部分子树，size[u] 算错，重心判定全崩。常见坑是读入后只加单向边，或用 vector<int> g[N]</int> 但下标越界（比如节点编号从 1 开始却用了 g[0] 存）。
建议统一用：
cin >> n;
g.resize(n + 1);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
重心本身不依赖根，但 DFS 必须选一个起点（比如 1），靠 fa 参数避免来回走。这个细节一旦写错，size 就全乱了。
