子树大小

一句话理解

子树大小 sz[u]=1+∑sz[son]。

为什么要学

重心、点分治、树剖。

讲解

后序累加。整棵树 sz[root]=n。

例子

void dfs(int u, int f) {
    sz[u] = 1;
    for (int v : g[u]) if (v != f) {
        dfs(v, u);
        sz[u] += sz[v];
    }
}

先算儿子再加到自己。

常见错误

• 先加后递归，sz 全是 1。
• 把父亲的 sz 也加进来。