题意

$n$ 个点的树 每个点有一个体积 $v_i$ 和收益 $w_i$。

只能选择不相邻的物品 要求你输出 $\forall i \in [1,m]$，容量为 $i$ 的背包收益最大的方案数

$n \leq 50,m \leq 5000$

题解

很 naive 的 dp 大概是 $f[i][j][0/1] $ 表示处理 $i$ 号点子树 已经用了 $j$ 容量，是否选择这个点的方案数 转移的时候搞个树形背包 复杂度 $O(nm^2)$

官方题解看起来很强大。。。

我们考虑沿用树形背包的一贯做法：按照 dfs 序来 dp。发现在 dp 过程中 一个点能不能选只取决于它的 father 是否选了 但是如果只记录 father 的值的话根本转移不了（$i \to i+1$的时候你不知道dfs序是 $i+1$ 的点上面的情况）、暴力的记录整个树复杂度就爆炸了，一个稍微好一点的想法是注意到 dfn 相邻的点的移动轨迹一定是往上跳若干步然后往下走一步（这个性质很有用），所以我们只需要记录这个点到根的路径上是否被选择就好了。

但是这样显然还是会被链卡没。

官方题解告诉我们先进行轻重链剖分 然后划定 dfs 序的时候最后遍历重儿子 这样你在 $i \to i+1$ 的时候会直接跳过上面的一段重链，所以我们发现对于每个点只需要记录每个重链的链底就好了 根据轻重链剖分的性质 这个数量就是一个点到根轻边的数量 是 $O(\log n)$ 的。

于是设 $f[i][S][j]$ 表示考虑到了 dfn 为 $i$ 的点 当前到根的链底的点的状态是 $S$ ，已经用了容量 $j$ ，$S$的状态数是 $O(2^{\log n}) = O(n)$ 的，转移可以写成 $O(1)$ 所以复杂度变成了 $O(n^2m)$

转移不会写 看了个代码 于是决定加一加注释加深理解

Code：

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
const int MAXM = 5000+5;

int n,m;
int a[MAXN],b[MAXN];// 重量 收益

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int sz[MAXN],son[MAXN];

inline void dfs1(int v,int fa=0){
    sz[v] = 1;son[v] = 0;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs1(e[i].to,v);sz[v] += sz[e[i].to];
        if(sz[son[v]] < sz[e[i].to]) son[v] = e[i].to;
    }
}

int ts;
int dfn[MAXN],nfd[MAXN],tp[MAXN],fa[MAXN];

inline void dfs2(int v,int ntp,int fa=0){
    dfn[v] = ++ts;nfd[dfn[v]] = v;tp[v] = ntp;
    ::fa[v] = fa;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to != fa && e[i].to != son[v]){
            dfs2(e[i].to,e[i].to,v);
        }
    }
    if(son[v]) dfs2(son[v],ntp,v);
}

struct Node{
    int f;LL g;
    Node(int f=0,LL g=0) : f(f),g(g) {}
}f[2][MAXN][MAXM],ans[MAXM];

inline void update(Node &x,const Node &y){
    if(x.f > y.f) return;
    if(x.f < y.f) x = y;
    else x.g += y.g;
}

int now;
std::vector<int> cha[MAXN];
int t1[MAXN];

inline void Solve(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d%d",a+i,b+i);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs1(1);dfs2(1,1);
    FOR(i,1,n){
        cha[i].clear();
        int t = i;
        while(t) cha[i].pb(t),t = fa[tp[t]];
    }
    CLR(f,0);
    f[now][0][0] = Node(0,1);
    FOR(i,1,n){
        int t = 0;
        int fat = -1;
        FOR(S,0,(1<<cha[nfd[i]].size())-1) FOR(k,0,m) f[now^1][S][k] = Node(0,0);
        for(auto x:cha[nfd[i-1]]){
            if(x == fa[nfd[i]]) fat = t;
            t1[t] = -1;
            FOR(j,0,(int)cha[nfd[i]].size()-1){
                if(cha[nfd[i]][j] == x){
                    t1[t] = j;
                    break;
                }
            }
            ++t;
        }
        // 转移时主要目的是得到 S 的后继状态 nxt 
        // 首先处理出任意一个点需要记录的点的集合 记做 cha[i] 那么cha[i-1]和cha[i]的交的状态就一定确定好了 现在就是确定当前点的状态和 father 的状态（判断是否转移）
        // 于是 t1[i] 存 nfd[i-1] 的第 i 位是 nfd[i] 的哪一位（或者不存在）转移即可
        FOR(S,0,(1<<cha[nfd[i-1]].size())-1){
            int nxt = 0;
            FOR(j,0,(int)cha[nfd[i-1]].size()-1)
                if((S>>j)&1 && t1[j] != -1) nxt |= (1<<t1[j]);
            FOR(k,0,m){
                if(f[now][S][k].g){
                    update(f[now^1][nxt][k],f[now][S][k]);
                    if(!((S>>fat)&1) && k+a[nfd[i]] <= m){
                        update(f[now^1][nxt|1][k+a[nfd[i]]],Node(f[now][S][k].f+b[nfd[i]],f[now][S][k].g));
                    }
                }
            }
        }
        now ^= 1;
    }
    FOR(i,0,m) ans[i] = Node(0,0);
    FOR(S,0,(1<<cha[nfd[n]].size())-1){
        FOR(i,0,m){
            update(ans[i],f[now][S][i]);
        }
    }
    FOR(i,1,m) printf("%lld%c",ans[i].g," \n"[i==m]);
    FOR(i,0,n) head[i] = dfn[i] = nfd[i] = 0;cnt = 0;ts = 0;
}

int main(){
    int T;scanf("%d",&T);
    FOR(i,1,T) printf("Case %d:\n",i),Solve();
    return 0;
}

More Things

我看到知乎上出题人说希望这个题成为以后题目的一种套路。。

这类套路大概就是将树 dp 转移到 dfn 上去做 如果只和父亲有关的话就可以用这个优化

所以以后做树 dp 的时候还是要考虑 dfn