[JZOJ4202] Shopping

Description

Solution

简化题意就是选择一个树上的联通块，这个联通块中所有商店至少买一个做背包

树上联通块问题往往可以通过点分治转化成树形依赖问题

先对于整棵树点分治，每个分治中心分别作为当前分治子树的根来树形依赖背包就可以了

多重背包可以拆分成log个独立的物品来考虑
好像还有一种单调队列的做法可以省掉这个log?

复杂度O(NMlognlogd)$O(NM\log n\log d)$
只要不是写的太丑基本上都能通过

Code

#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 505
#define R 4005
#define LL long long
using namespace std;
int n,m,t,w[N],m1,c[N],r[N],nt[2*N],dt[2*N],fs[N],f[N][R],g[R],ans,sz[N],mi,mw,dfn[N],vl[N][20],h[R];
bool bz[N];
void link(int x,int y)
{
    nt[++m1]=fs[x];
    dt[fs[x]=m1]=y;
}
void find(int k,int fa,int num)
{
    sz[k]=1;
    int mx=0;
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(p!=fa&&!bz[p])
        {
            find(p,k,num);
            sz[k]+=sz[p];
            mx=max(mx,sz[p]);
        }
    }
    if(max(mx,num-sz[k])<mi) mw=k,mi=max(mx,num-sz[k]);
}
void dfs(int k,int fa)
{
    sz[k]=1;
    dfn[++dfn[0]]=k;
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(p!=fa&&!bz[p])
        {
            dfs(p,k);
            sz[k]+=sz[p];
        }
    }
}
void doit(int k,int num)
{
    bz[k]=1;
    dfn[0]=0;
    dfs(k,0);
    fo(i,1,dfn[0]+1) fo(j,0,m) f[i][j]=0;  
    fod(i,dfn[0],1)
    {
        int p=dfn[i];
        fo(j,0,m) g[j]=f[i+1][j],h[j]=0;
        fo(x,1,vl[p][0])
        {   
            fod(j,m,vl[p][x]*c[p])
            { 
                h[j]=max(h[j],g[j-vl[p][x]*c[p]]+vl[p][x]*w[p]);
                g[j]=max(g[j],h[j]);
            }
        }
        fo(j,1,m) f[i][j]=max(f[i][j-1],max(h[j],f[i+sz[p]][j]));
    }
    ans=max(ans,f[1][m]);
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(!bz[p])
        {
            mi=num;
            find(p,k,sz[p]);
            doit(mw,sz[p]);
        }
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        fo(i,1,n) scanf("%d",&w[i]);
        fo(i,1,n) scanf("%d",&c[i]);
        memset(vl,0,sizeof(vl));
        fo(i,1,n) 
        {
            scanf("%d",&r[i]);
            int l=r[i];
            vl[i][0]=1,vl[i][1]=1,l--;
            while(l>=vl[i][vl[i][0]]*2)
            {
                vl[i][++vl[i][0]]=vl[i][vl[i][0]-1]*2;
                l-=vl[i][vl[i][0]];
            }
            if(l) vl[i][++vl[i][0]]=l;
            sort(vl[i]+1,vl[i]+vl[i][0]+1);
        }
        ans=0;
        m1=0;
        memset(bz,0,sizeof(bz));
        memset(nt,0,sizeof(nt));
        memset(fs,0,sizeof(fs));
        fo(i,1,n-1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            link(x,y);
            link(y,x);
        }
        memset(f,0,sizeof(f));
        mi=n;
        find(1,0,n);
        doit(1,n);
        printf("%d\n",ans);
    }
}