‹ 上一题 下一题 ›

g6-07125. 子树统计·初值语句的位置 未做

1000 ms 256 MB 测试点 ? 通过率 50% 自拟题知识点题GESP-66级·深度优先搜索客观题单选

用下面的代码统计子树大小,从根调用 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 上方那一块」 的大小,为求重心做准备
未选择
输入
输出

            
答案