[题解] P8564 ρars/ey

· · 题解

\color{red}博客内食用效果更佳（点我）

思路：树上背包

复杂度：O(n^2)

题解中涉及到的变量：

变量名 含义
val_i 操作代价（题目给出的）
f_{i,j} 对于节点 i 的子树，删去 j 个节点的最小代价

主体思路

操作代价与当前子树大小相关，不难想到用树上背包去解决此问题，设 f_{now,j} 表示对于节点 now，删去 j 个节点的最小代价。

当不对当前节点进行删除操作时：

转移方程：

f_{now,j}=\max_{0\le k\le j}\{f_{son,k}+f_{now,j-k}\}

注意到这样转移复杂度不够优，考虑控制上下界，设 siz_{now} 表示枚举到当前子节点之前的子树大小，siz_{son} 为当前子节点大小，cnt 为枚举到的子节点个数。有 j,k 范围：

1\le j\le siz_{now}+siz_{son}-1-cnt \max\{1,j-siz_{now}\}\le k\le\min\{siz_{son}-1,j\}

当对当前节点进行删除操作时：

转移方程（其中 siz_{now} 表示当前节点子树大小）：

f_{now,siz_{now}-1}=\min_{0\le j\le siz_{now}-2}\{f_{now,i}+val_{siz_{now}-1-i}\}

代码实现需要注意的地方：

参考代码：

代码中的 to 为 son。
参考代码中其他变量名与题解中均一致，详见注释。

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=5005;

int n,val[N];
//--------------------//
//Edge
const int M=1e4+5;

struct Edge
{
    int to,nex;
}edge[M];
int tot,head[N];
void add(int from,int to)
{
    edge[++tot]={to,head[from]};
    head[from]=tot;
}
//----------//
//DP
LL f[N][N];
int siz[N];
void DFS(int now,int fa)
{
    siz[now]=1;
    f[now][0]=0;
    for(int to,cnt=0,i=head[now];i;i=edge[i].nex)
    {
        to=edge[i].to;
        if(to==fa)
            continue;
        DFS(to,now);
        cnt++;//更新子节点个数
        for(int j=siz[now]+siz[to]-1-cnt;j>0;j--)//倒序枚举，上下界优化
            for(int k=max(j-siz[now],1);k<=min(siz[to]-1,j);k++)
                f[now][j]=min(f[now][j],f[now][j-k]+f[to][k]);//转移
        siz[now]+=siz[to];//更新子树大小
    }
    for(int i=0;i<siz[now]-1;i++)//对当前节点进行操作的最小代价
        f[now][siz[now]-1]=min(f[now][siz[now]-1],f[now][i]+val[siz[now]-1-i]);
}
//--------------------//
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        scanf("%d",&val[i]);
    for(int from,to,i=1;i<n;i++)
        scanf("%d%d",&from,&to),add(from,to),add(to,from);
    DFS(1,0);
    printf("%d",f[1][siz[1]-1]);//答案，显著的
    return 0;
}