用下面的代码统计子树大小,从根调用 dfs(根, 0)(0 表示根没有爸爸):
void dfs(int u, int fa) {
sz[u] = 1;
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
关于第一句 sz[u] = 1 的作用与位置,下列说法正确的是( )。
- A. 它只对根节点有意义,其他点的 sz 全靠孩子累加,非根点不需要这句
- B. 它对每个进入的点都执行:先记「子树里至少有我自己」,等每个孩子返回后再把 sz[v] 逐个收进来
- C. 应该把它挪到递归调用之后执行,否则累加的结果会被 1 覆盖
- D. 它算的是「u 上方那一块」 的大小,为求重心做准备