almost copied from 英才计划论文.

定义

一般来说，树形背包的问题可以抽象为如下形式：

给定 n 个物品，物品间的选择存在依赖关系，以依赖关系的边可以构成一棵树。

现在请你选择 k 个物品使得选择价值最大。

我们先定义状态 f_{x,i} 表示点 x 体积为 i 的状态。

这个问题本质上等价于一个分组背包模型，即儿子集合内每个状态 f_{y,j} 可以被视为一个体积为 j，价值为 f_{y,j} 的物品，而每个子树设为一个组，那么转移方程显然就是：

f_{x,k} = \max\limits_{\sum\limits_{i = 1}^p c = t-1} \sum\limits_{i=1}^p f_{y,c} + val(x)

暴力转移，我们容易得到复杂度是 \mathcal{O}(nk^2)的。

优化

我们考虑转移复杂度劣的原因，实际上会使得每个节点都会在父节点处被处理，所以相当于每个父节点处都会计算子树内所有节点的值。故上述方程容易被特殊构造的链状数据卡到最差 O(n^3) 的复杂度。

所以我们需要控制枚举的上界，具体来说，不妨假设存在全选子树内的节点的情况，那么在过程中完成 y(y \in s(x)) 到 x 的转移后，x 的枚举上界应为 |s(x)| + |\text{subtree}(y)| ，此处 \text{subtree}(y) 表示以 y 为根的子树。y 的枚举上界应为 \min\{|\text{subtree}(y)|,chos-1\}，其中 chos 是上文提到的枚举 x 的子树内选择个数。

上文的实现方式实际上还是会存在枚举到不合法的情况，故我们需要进行一个类似卷积的过程。对于一个节点 x 和 y(y \in s(x))，在过程中枚举 x 的选择点数 i 和 y 的选择点数 j，并且用一个临时数组存储下 f_{x,i} 和 f_{y,j} 的和，每次用 f_{x,i} 和 f_{y,j} 来更新 i+j 并且取最小值。

此处给出伪代码实现参考：

//In C++
//subtree[x] 代表上文提到的子树大小
//f[x][k] 表示上文提到的状态转移
for (int i = subtree[x];i >= 0;--i) {
    for (int j = subtree[y];j >= 0;--j) {
        tmp[i+j] = max(tmp[i+j],f[x][i] + f[y][j]);
    }
}
for (int i = subtree[x];i >= 0;--i) {
    f[x][i] = tmp[i];
}
subtree[x] += subtree[y];

上文提到的转移方法的时间复杂度是 \Theta(nk) 的，此处给出证明。

(参考：cervoliu-子树合并背包类型的dp的复杂度证明 https://blog.csdn.net/lyd_7_29/article/details/79854245)

定义大小超过 k 的子树为大子树，反之为小子树。

一个极小的大子树一定是由若干个极大的小子树合并而成的，而且合并的过程中就会从极大的小子树变成极小的大子树。

假设所有的极大的小子树的大小分别为x_1,x_2,x_3,\dots.x_m，显然 x_1+x_2+…+x_m\leq n，将这些小子树并入大子树的复杂度为 k\times (x_1+x_2+…+x_m)\leq n_k，可以认为是每个极大的小子树被消灭掉所产生的总时间代价不超过 nk。

考虑一个极大的小子树（大小 x\leq k）内部合并上来的复杂度，由上面的分析知是x^2 的。 因此每个小子树内部合并的复杂度就是x_1^2+x_2^2+\dots +x_m^2,xi\leq k，显然当尽量多的 x_i 取到 k 这个值才会更大，因为假设\sum\limits_{1\leq i\leq n} x_i = n为定值，x_1>x_2，如果让x_1+1,x_2–1，上面那个值会变大。这样复杂度就是\Theta(\frac{n}{k} \times k^2) = \Theta(nk)

最后，考虑将所有的极小大子树合并成整棵树的复杂度，显然极小的大子树互不包含，因此极小的大子树个数不会超过 \frac{n}{k} 个，而每合并两个的时间开销是 k^2 ，因此这部分复杂度是 \Theta(\frac{n}{k} \times k^2) = \Theta(nk)

例题

Luogu P3177 HAOI2015 树上染色

有一棵点数为 n 的树，树边有边权。给你一个在 0 \sim n 之内的正整数 k ，你要在这棵树中选择 k 个点，将其染成黑色，并将其他 的 n-k 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

n,k \leq 2000

我们考虑从边的角度来思考，那么原题所求的就变成了求每条边被一对黑点或一对白点经过几次。考虑把边左右端点分成两棵树，那么答案就是左边黑点数 右边黑点数 + 左边白点数 右边白点数。

接下来考虑，每个点被决策成为黑点/白点对答案造成的影响。我们设左边子树的黑点有 m 个，则易得右边子树的黑点有 k-m 个，那么容易计算：

ans = m \times (k-m)+(siz_l-k)\times(n - k - (siz_l - k))

那么我们考虑，我们把这个过程放到树上来考虑。我们依然设计经典的 f_{x,i} 表示点 x 子树内有 i 个黑点，转移的时候我们只需要讨论 (x,y) 这条边的贡献就可以了。也就是转移：

f_{x,i} = \max\limits_{j = 0}^i{f_{x,i-j} + f_{y,j} + ans * w_{(x,y)}}

利用上方转移，我们可以做到时间复杂度 \mathcal{O}(n^2)。

const int N = 2010; 
const int M = N<<1;
int hd[N],edg[M],nxt[M],to[M],tot;
int siz[N],n,m;
ll f[N][N];

inline void add(int u,int v,int w) {
    edg[++tot] = w;to[tot] = v;nxt[tot] = hd[u];hd[u] = tot;
}

inline void addedge(int u,int v,int w) {
    add(u,v,w);add(v,u,w);
}

void dfs(int x,int fa) {
    siz[x] = 1;f[x][0] = f[x][1] = 0;
    for (int i = hd[x];i;i = nxt[i]) {
        int y = to[i];
        if (fa == y) continue;
        dfs(y,x);
        siz[x] += siz[y];
        for (int j = min(siz[x],m);j >= 0;--j) {
            if (f[x][j] != -1) {
                f[x][j] += f[y][0] + (ll)siz[y] * (n-m-siz[y]) * edg[i];
            }
            for (int k = min(siz[y],j);k > 0;--k) {
                if (f[x][j-k] == -1) continue;
                ll tmp = (m-k)*k+((n-m)-(siz[y]-k))*(siz[y]-k);
                f[x][j] = max(f[x][j],f[x][j-k] + f[y][k] + tmp * edg[i]);
            }
        }
    }
}

int main() {
    read(n,m);
    if(n-m<m)m=n-m;
    for (int i = 1;i < n;++i) {
        int x,y,z;
        read(x,y,z);
        addedge(x,y,z);
    }
    memset(f,-1,sizeof(f));
    dfs(1,0);
    printf("%lld",f[1][m]);
    return 0;
}

一道题

一棵 n 个点的树（n 为偶数），将树上的点两两匹配。也就是说对于任意一个结点 u，有且仅有一个结点 v 与之配对。

对于匹配有一些限制。对于两个匹配 (u,v) 和 (x,y)，婷姐要求这两个匹配要么相离，要么一个包含另一个。

• 相离：u 到 v 的路径与 x 到 y 的路径不相交。
• 包含：u 到 v 的路径包含 x 到 y 的路径或者 x 到 y 的路径包含 u 到 v 的路径。

婷姐需要你告诉他，这样的匹配一共有多少种方案。答案对 998244353 取模。

两个方案不同当且仅当存在某个结点，使得在这两个方案中与它配对的那个结点不同。

n \leq 2000

这道题乍看很难联系到树形背包上，所以我们先设计一个暴力的状态 f_{x,i} 表示我们考虑从 x 出发的一条长度为 i 的链。

我们考虑怎样刻画一个匹配，可以发现，我们考虑一条链 (u,v)，实际上可以从他们的一个“中转点” x 来考虑。假设 len_{(u,x)} = i,len_{(x,v)} = j，那么我们就有

f_{x,i + j+1} = val_{(u,v)}\times (f_{u,i} + f_{v,j})

可以发现，这个本质上是一个只考虑两个子树的背包合并！