自动搬运

查看原文

来自洛谷，原作者为

	gcx12012 每一个不曾起舞的日子，都是对生命的辜负。

搬运于2025-08-24 23:15:36，当前版本为作者最后更新于2025-05-07 22:45:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

不太正常的树形 dp。

Solution

这里假定 $n,k$ 同阶。

首先 $O(n^3)$ 的树形背包是好想的，这里就不多说了。

然后发现树形背包的做法不太好优化至 $O(n^2)$，于是考虑改变转移方式。

这个题求的是有关包含点 $1$ 联通块的最大价值，于是考虑由某个节点转移到它的若干儿子。

这里推荐一个 dfs 写法：设当前考虑到节点 $u$，要转移到的儿子节点为 $v$，我们考虑先 $O(n)$ 转移到节点 $v$，然后直接递归至 $v$，到处理完子树 $v$ 后将 $f_u$ 的对应位置和子树内的每一个 $f_i$ 取 $\max$。

这样还是 $O(n^3)$ 的，此时我们可以在回溯的过程中将$f_u$ 直接和 $f_v$ 取 $\max$，这样是对的，因为经过这样的操作之后子树 $v$ 的 $f$ 已经预处理好了。

这么做是 $O(n^2)$ 的，完全可以通过，并且代码很短。

vector<int >e[N];
ll f[N][N],a[N],b[N];
int n,m;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void dfs(int u){
	for(int v:e[u]){
		For(i,0,m){
			if(i+1<=m) f[v][i+1]=max(f[v][i+1],f[u][i]);
			if(i+b[v]<=m) f[v][i+b[v]]=max(f[v][i+b[v]],f[u][i]+a[v]);
		}
		dfs(v);
		For(i,0,m) f[u][i]=max(f[u][i],f[v][i]);
	}
}

int main()
{
    //freopen("gcx.in","r",stdin);
    //freopen("gcx.out","w",stdout);
    n=read(),m=read();
    For(i,1,n){
    	For(j,0,m){
    		f[i][j]=-1e15;
    	}
    }
    For(i,2,n){
    	int u=read();
    	e[u].pb(i);
    }
    For(i,1,n) a[i]=read();
    For(i,1,n) b[i]=read();
    f[1][1]=0,f[1][b[1]]=a[1];
    dfs(1);
    ll ans=-1e15;
    For(i,0,m) ans=max(ans,f[1][i]);
    cout<<ans;
   	return 0;
}