题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

· · 题解

前言

不太正常的树形 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;
}