g7-07708. 树形背包的复杂度 未做

$dp[u][j]$ 表示在 $u$ 的子树里选 $j$ 个节点的最优值，容量上限 $K=n$。合并儿子的代码如下：

void dfs(int u, int fa) {
    dp[u][0] = 0; sz[u] = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int j = min(sz[u], K); j >= 0; j--)
            for (int k = 0; k <= min(sz[v], K - j); k++)
                dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
        sz[u] += sz[v];
    }
}

单看嵌套的层数，每个节点都有一层 $j$、一层 $k$，合起来像是 $O(n^3)$。它实际是 $O(n^2)$ 的原因是（ ）。

• A. 因为 $k$ 的上界被 $K-j$ 限制，三层循环的实际次数约为 $n^3/2$，只是常数变小了
• B. 因为每一对节点只会在它们的 LCA 处被合并一次，总配对数不超过 $n(n-1)/2$，所以是 $O(n^2)$
• C. 因为每个状态只被访问一次，三层循环的循环体总共只执行 $n$ 次
• D. 因为树只有 $n-1$ 条边，是稀疏图，所以复杂度与边数同阶，是 $O(n)$