树的重心是删除后使剩余连通块最大节点数最小的节点，可能有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 已建好）：
int n;
vector<vector>> 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 <h3>多个重心怎么处理，<code>vector<int></int></code> 还是只取一个</h3>
<p>一棵树最多有两个重心，且一定相邻。如果你只需要任一重心（比如做点分治的根），取 <code>centroid[0]</code> 即可；如果需全部，保留整个 <code>centroid</code> vector。注意：当 <code>n</code> 为偶数且存在两个重心时，它们分割出的各连通块 size 都等于 <code>n/2</code>，此时 <code>max_subtree == n/2</code>，仍满足 ≤ <code>n/2</code> 条件，不会被漏掉。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>性能上无差异，但逻辑上必须允许重复收集——不能遇到第一个就 <code>return</code>。</p>
<h3>输入是无向边，建图时要不要加双向边</h3>
<p>要。树是无向图，<code>g[u].push_back(v)</code> 和 <code>g[v].push_back(u)</code> 都必须有。否则 DFS 会漏掉部分子树，<code>size[u]</code> 算错，重心判定全崩。常见坑是读入后只加单向边，或用 <code>vector<int> g[N]</int></code> 但下标越界（比如节点编号从 1 开始却用了 <code>g[0]</code> 存）。</p>
<p>建议统一用：</p>
<pre class="brush:php;toolbar:false;">
cin >> n;
g.resize(n + 1);
for (int i = 1; i > u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
重心本身不依赖根，但 DFS 必须选一个起点（比如 1），靠 fa 参数避免来回走。这个细节一旦写错，size 就全乱了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
