https://www.luogu.org/problemnew/show/P2014
树形背包的裸题。。当版子好了。
$f[i][j][k]$表示子树$i$选前$j$个孩子，共$k$个后代节点时的最大价值。然后$j$那一维是可以滚动的（但同时也要注意枚举变成了倒序），所以可以去掉。
$f[i][j]$表示子树$i$共选$k$个后代节点时的最大价值。
然后每个点可以抽象为一个背包，他的每个孩子包含一组物品，一组物品中包括以孩子为子树，选v个其后代节点形成的最大价的共v+1个物品（1指的是只有孩子自己）。对于每个孩子，只能选他的一种状态情形，或者不选。所以就是一个分组背包啦。
但是注意，子树的根必须强制选上。所以可以以他为初态，也就是后代节点=0的状态。写一下伪代码。
$dp$ $i$
$f_{i,0}=w_i$初态
$for$ $j=1$～$son_i$
$for$ $k=sum_j -1～1$
$for$ $v=0$～$sum_j -1$
$if$ $v+1\leqslant k$
$f_{i,k}=max\{f_{i,k-v-1}+f_{j,v}\}$
然后复杂度由于是每个点都被考虑一次的，最坏是$O(n^3)$。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl 9 using namespace std; 10 typedef long long ll; 11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline T read(T&x){ 16 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c==‘-‘)f=1; 17 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 18 } 19 const int N=300+7; 20 int f[N][N],Head[N],Next[N<<1],v[N<<1],w[N],sum[N],tot; 21 int n,m; 22 inline void Addedge(int x,int y){ 23 v[++tot]=y,Next[tot]=Head[x],Head[x]=tot; 24 v[++tot]=x,Next[tot]=Head[y],Head[y]=tot; 25 } 26 void dp(int i,int fa){ 27 sum[i]=1; 28 for(register int tmp=Head[i],j=v[tmp];tmp;tmp=Next[tmp],j=v[tmp])if(j!=fa)dp(j,i),sum[i]+=sum[j]; 29 f[i][0]=w[i]; 30 for(register int tmp=Head[i],j=v[tmp];tmp;tmp=Next[tmp],j=v[tmp])if(j!=fa){ 31 for(register int k=sum[i]-1;k;--k){ 32 for(register int v=0;v<=sum[j]-1;++v) 33 if(v+1<=k)MAX(f[i][k],f[i][k-v-1]+f[j][v]); 34 } 35 } 36 } 37 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 38 read(n),read(m);int x; 39 for(register int i=1;i<=n;++i)read(x),read(w[i]),Addedge(x,i); 40 dp(0,0);printf("%d\n",f[0][m]); 41 return 0; 42 }
原文：https://www.cnblogs.com/saigyouji-yuyuko/p/10700556.html