零、写在前面

不想跑模型，水了下群友扔的题。发现是一个很裸的树上背包，大概分析下复杂度就ac了。

忽然想起来去年也写过类似的一道树上背包，当时对于复杂度是非常疑惑的，始终无法理解时间复杂度是O(N^2)。

今天反而一下就分析出来了，正好记录一下。

一、P1273 的复杂度分析

一眼树上背包：

• 当前递归到子树 u

• 定义 f[j] 为 子树 u 内选了 j 个用户的最大净收益，那么对于 u 的邻接点v，可做如下背包合并：

  • for (int i = siz[v]; i >= 0; --i) {
        for (int j = siz[u]; j >= 0; --j) {
        	nf[i + j] = std::max(nf[i + j], f[j] + g[i] - (i > 0 ? w : 0));
        }
    }
    

    g[i] 代表子树v 内选 i 个用户的最大净收益

所以不难写出这个解法：

#include <bits/stdc++.h>
namespace ranges = std::ranges;
namespace views = std::views;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<std::array<int, 2>>> adj(N);
    for (int i = 0; i < N - M; ++i) {
        int m;
        std::cin >> m;
        while (m-- > 0) {
            int v, w;
            std::cin >> v >> w;
            --v;
            adj[i].push_back({v, w});
        }
    }
    std::vector<int> val(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> val[i];
    }
    std::vector<int> siz(N);
    auto dp = [&](this auto &&self, int u, int p) -> std::vector<int> {
        siz[u] = 1;
        std::vector<int> f(2, -1E9);
        f[0] = 0;
        if (u >= N - M) {
            f[1] = val[u - (N - M)];
        }
        for (auto &[v, w] : adj[u]) {
            if (v == p) {
                continue;
            }
            auto g = self(v, u);
            std::vector<int> nf(siz[u] + siz[v] + 1, -1E9);
            nf[0] = 0;
            for (int i = siz[v]; i >= 0; --i) {
                for (int j = siz[u]; j >= 0; --j) {
                    nf[i + j] = std::max(nf[i + j], f[j] + g[i] - (i > 0 ? w : 0));
                }
            }
            siz[u] += siz[v];
            f.swap(nf);
        }
        return f;
    }(0, -1);
    int ans = 0;
    for (int i = 0; i < dp.size(); ++i) {
        if (dp[i] >= 0) {
            ans = i;
        }
    }

    std::cout << ans << '\n';

    return 0;
}

如何分析时间复杂度？

瓶颈在于遍历邻接点v时的二重循环：

for (auto &[v, w] : adj[u]) {
    if (v == p) {
        continue;
    }
    for (int i = siz[v]; i >= 0; --i) {
        for (int j = siz[u]; j >= 0; --j) {
        }
    }
}

1.1 纯数学视角：

假设节点 u 有 $k$ 个子节点，它们的子树大小分别为 $s_1,s_2,s_3,\dots ,s_k$。

代码在合并子节点时，是逐个合并的：

• 最开始，siz[u] 只有节点 u 自己，大小为 $1$。
• 合并第 1 个子节点时，执行次数是 $s_1\times 1$。合并后 siz[u] 变成了 $1+s_1$。
• 合并第 2 个子节点时，执行次数是 $s_2\times (1+s_1)$。合并后 siz[u] 变成了 $1+s_1+s_2$。
• 合并第 $m$ 个子节点时，执行次数是 $s_m\times (1+s_1+\cdots +s_{m-1})$。

我们把节点 u 本身看作 $s_0=1$。
那么，在节点 u 上为了合并所有子树，嵌套循环的总执行次数就是：
$$\begin{array}{rl}& \sum _{i=1}^k\left(s_i\times \sum _{j=0}^{i-1}{s}_j\right)\\ & <size[u{]}^2\end{array}$$
因为 $$\sum _{u=0}^{N-1}size[u]=N$$

所以 $$O(\sum _{u=0}^{N-1}size[u{]}^2)=O(N^2)$$

1.2 组合数学视角

for (int i = siz[v]; i >= 0; --i)
    for (int j = siz[u]; j >= 0; --j)

• siz[v] 代表子节点 $v$ 的子树中的节点个数。
• siz[u] 代表在合并 $v$ 之前，节点 $u$ 已经合并好的节点个数（包括 $u$ 自己和它前面的子树）。

siz[v] * siz[u] 的实际组合意义是：从 $v$ 的子树中随便挑一个节点 $x$，再从 $u$ 当前已经合并的子树中随便挑一个节点 $y$，把它们配成一对 $(x,y)$。

嵌套循环每执行一次（即 i 和 j 的某一次组合），本质上就相当于把节点 $x$ 和节点 $y$ 在这里“相遇”并处理了一次。

换句话说：
整棵树的所有节点构成的每一对配对 $(x,y)$，在整个 DFS 的过程中，有且仅有一次会在这个嵌套的 for 循环中被计算到。

一共有 $N$ 个节点，配对的总对数是组合数 $C_N^2=\frac{N(N-1)}{2}$。
既然每一对只会被计算一次，那么整个程序中这两个嵌套 for 循环内部代码的全局总执行次数，严格等于 $\frac{N(N-1)}{2}$。

所以，该代码的整体复杂度为$O(N^2)$