概念

树形背包，就是说，在树上选一个包含根的连通块，或背包存在依赖关系（选父才能选子），或者需要知道每个点的子树中选了多少……
通常，我们有两种方法：

一、基于dfs合并：

我们设\(dp(i,j)\)表示在i的子节点中选j个的状态。
在转移时，先dfs子节点，然后依次把子节点合并，每次合并2个。
即枚举\(a,b\)，用\(dp(i,a)\)和\(dp(son,b)\)组合为\(f(a+b)\)，每次合并后，把f赋给dp。

下面分析时间复杂度：

1、物品大小为1，没有限制：

（伪）代码：

void Tree_Dp(int p)
{
    size[p]=1;
    each(x,son[p])
    {
        Tree_Dp(x);
        for(int i=0;i<=size[p];++i)
            for(int j=0;j<=size[x];++j)
                update dp[p][i+j];
        size[p]+=size[x];
    }
}

时间复杂度为\(O(n^2)\)。
考虑那个二重循环，可以看做分别枚举两棵子树的每个点。可以发现，点对\((u,v)\)，只会在\(Tree_Dp(lca(u,v))\)处被考虑到，所以复杂度是\(O(n^2)\)。

2、有物品大小：

（伪）代码：

void dfs(int x)
{
    sum[x]=c[x];dp[x][c[x]]=v[x];
    if(!he[x])
        return;
    for(int i=he[x],t;i;i=e[i].ne)
    {
        t=e[i].to;dfs(t);
        sum[x]+=sum[t];
        for(int s1=min(sum[x],lim);s1>=c[x];s1--)
        {
            for(int s2=min(sum[t],min(s1-c[x],lim));s2>=c[t];s2--)
                dp[x][s1]=max(dp[x][s1],dp[x][s1-s2]+dp[t][s2]);
        }
    }
}

这个复杂度我也不清楚，可以卡到\(O(n^3)\)，但是，在数据随机时是能跑过8000，1s的。

3、物品大小为1，有k的限制。

（伪）代码：

void dfs(int u, int fu) {
    int si = 0;
    for (int i = fr[u]; i != -1; i = ne[i]) {
        if (v[i] != fu) 
            dfs(v[i], u);
    }
    for (int i = fr[u]; i != -1; i = ne[i]) {
        if (v[i] == fu) continue;
        int rt = sz[v[i]];
        for (int a = 0; a <= min(si, k); a++) {
            for (int b = 0; b <= min(rt, k - a); b++) {
                   //转移dp
            }
        }
        si += rt;
    sz[u] = si + 1;
}
这个算法，最初觉得是$O(nk^2)$的，实际上是$O(nk)$的。
### 复杂度证明：
1. 根据正常树形背包的复杂度$O(n^2)$，小于等于k的最多产生$n/k*k^2$的复杂度。
2. 大于k与大于k的合并一次，被合并的就增加k，最多n/k次，最多产生$n/k*k^2$的复杂度。
3. 大于k的与小于等于k的合并时，每个小于等于k的最多被合并一次，所以是$n*s_1+n*s_2+...+n*s_m$，也是$nk$。

#### 还有一种理解：
把树按照dfs序变为序列。
然后，在子树中枚举取x个，可以理解为取dfs序的前（后）x个。
而合并时，认为一棵子树取后x个，另一棵取前y个。$(x+y\leq k)$。这可以合并为长x+y的区间。
这其实就是长度不大于k的子串，最多有nk个。
但是，因为有取0个的情况，所以实际做题时，大约有2的常数。但那个常数就忽略了可以。

二、dfs序上dp：

树形背包总结

原文：https://www.cnblogs.com/lnzwz/p/11519977.html