自动搬运

查看原文

来自洛谷，原作者为

	lhm_ sjzez 的一名 OI 学生

搬运于2025-08-24 22:19:42，当前版本为作者最后更新于2020-09-18 14:20:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑若连通块必须包含 $x$，那么就对以 $x$ 为根的有根树做树形背包。

设 $f_{i,j}$ 为考虑了 $dfs$ 序中 $[i,n]$ 对应的节点，体积为 $j$ 的最大价值。转移分两种情况：一个是选 $i$ 对应的节点，然后对该节点的物品跑多重背包，我这里用的是二进制拆分来优化。另一个是不选 $i$ 对应的节点，然后从该节点子树外转移过来，这里可以在 $dfs$ 序上表示转移的位置。

连通块不包含 $x$ 的情况可以用点分治来递归处理。

复杂度为 $O(nm\log d\log n)$。

#include<bits/stdc++.h>
#define maxn 1010
#define maxm 4010
using namespace std;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int T,n,m,ans,tot,root,cnt;
int w[maxn],c[maxn],d[maxn],f[maxn][maxm],siz[maxn],mx[maxn],out[maxn],rev[maxn];
bool vis[maxn];
struct edge
{
    int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
    e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
struct node
{
    int v,w;
}p[maxn];
void dfs_root(int x,int fa)
{
    siz[x]=1,mx[x]=0;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]||y==fa) continue;
        dfs_root(y,x),siz[x]+=siz[y];
        mx[x]=max(mx[x],siz[y]);
    }
    mx[x]=max(mx[x],tot-siz[x]);
    if(mx[x]<mx[root]) root=x;
}
void dfs_dfn(int x,int fa)
{
    rev[++cnt]=x;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]||y==fa) continue;
        dfs_dfn(y,x);
    }
    out[x]=cnt;
}
void solve(int x)
{
    vis[x]=true,cnt=0,dfs_dfn(x,0);
    for(int i=cnt;i;--i)
    {
        int s=d[rev[i]]-1,num=0;
        for(int j=1;j<=s;s-=j,j<<=1) p[++num]={w[rev[i]]*j,c[rev[i]]*j};
        if(s) p[++num]={w[rev[i]]*s,c[rev[i]]*s};
        for(int j=m;j>=c[rev[i]];--j) f[i][j]=f[i+1][j-c[rev[i]]]+w[rev[i]];
        for(int k=1;k<=num;++k)
            for(int j=m;j>=p[k].w;--j)
                f[i][j]=max(f[i][j],f[i][j-p[k].w]+p[k].v);
        for(int j=0;j<=m;++j) f[i][j]=max(f[i][j],f[out[rev[i]]+1][j]);
    }
    ans=max(ans,f[1][m]);
    for(int i=1;i<=cnt;++i)
        for(int j=0;j<=m;++j)
            f[i][j]=0;
    int now=tot;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]) continue;
        root=0,tot=siz[y];
        if(siz[y]>siz[x]) tot=now-siz[x];
        dfs_root(y,x),solve(root);
    }
}
void clear()
{
    edge_cnt=root=ans=0;
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
}
int main()
{
    read(T);
    while(T--)
    {
        clear(),read(n),read(m);
        for(int i=1;i<=n;++i) read(w[i]);
        for(int i=1;i<=n;++i) read(c[i]);
        for(int i=1;i<=n;++i) read(d[i]);
        for(int i=1;i<n;++i)
        {
            int x,y;
            read(x),read(y);
            add(x,y),add(y,x);
        }
        tot=mx[0]=n,dfs_root(1,0),solve(root),printf("%d\n",ans);
    }
    return 0;
}