P6326 Shopping

題意等價于要買一個連通塊。

首先如果我們能求出一個 dp 數(shù)組：
\(f_{i,j}\) 表示 \(i\) 子樹內(nèi)，有 \(j\) 元，一定要選 \(i\)，能得到的最大價值。
那么 \(f_{1,m}\) 就是一定選根的答案。
然后點(diǎn)分治即可。

接下來就是怎么在合理的復(fù)雜度內(nèi)求出 dp 數(shù)組。
直接背包顯然不行，因為這不是一個普通的樹形背包，他的第二維跟子樹大小無關(guān)，所以合并子樹的復(fù)雜度是單次 \(O(m^2)\)，總復(fù)雜度是 \(O(nm^2)\)。

然后就誕生了一種很厲害的科技——樹上依賴性背包。
因為選兒子就一定要選父親，所以管他叫這個名字。
具體做法是：
設(shè) \(f_{i,j}\) 表示考慮 dfn 位于 \([i,n]\) 中的點(diǎn)，有 \(j\) 元錢能得到的最大價值。
下面設(shè)根為 \(1\)。
因為根是 dfn 最小的點(diǎn)，它一定要選，特判一下。
接下來考慮 \(dfn=2\) 的點(diǎn)，不妨設(shè)為 \(2\)，他一定是 \(1\) 的兒子，他有兩種選擇：

1. 不選，那他子樹內(nèi)的點(diǎn)都不能選，而眾所周知，子樹內(nèi)的點(diǎn)的 dfn 是連續(xù)的一段區(qū)間，那么轉(zhuǎn)移就是：\(f_{2 + Size_2,j} \to f_{2,j}\)。
   此時剩下的問題相當(dāng)是把 \(2\) 這棵子樹去掉了，仍然是一棵樹，并且 dfn 也是一個后綴。
   并且如果在剩下的這棵樹內(nèi)選擇了一個連通塊，那么放到原樹內(nèi)選出的也是一個連通塊。
   所以他是一個子問題。
2. 選，轉(zhuǎn)移是：\(max_{1\le k \le d_2}(f_{3,j-c_2\times k} + w_2\times k) \to f_{2,j}\)。
   這個轉(zhuǎn)移本質(zhì)是多重背包，可以用二進(jìn)制拆分優(yōu)化到 \(O(\log d)\)，也可以用單調(diào)隊列優(yōu)化到均攤 \(O(1)\)。
   此時 \(1,2\) 構(gòu)成了一個連通塊，我們把它視為新的根，原本 \(1,2\) 的子樹接到這個新的根上。
   那么構(gòu)成的仍然是一棵樹，dfn 是一個后綴，且如果在這棵新樹里選出了一個連通塊，那么放到原樹上也是一個連通塊。
   所以它也是一個子問題。
   然后把新的根當(dāng)根繼續(xù)考慮 \(dfn=3\) 的點(diǎn)。

答案是 \(f_{1,m}\)。

這個 dp 是 \(O(nm\log d)\) 或者 \(O(nm)\) 的。
總復(fù)雜度乘一個點(diǎn)分治的 \(O(\log n)\) 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=500+5,M=4000+5,inf=0x3f3f3f3f3f3f3f3f;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,ans,w[N],c[N],d[N];
int tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
} 

int rt,sum,Size[N],maxn[N],rev[N],num,f[N][M],g[M];
bool vis[N];
void Get_zx(int u,int fa){
	Size[u]=1;
	maxn[u]=0;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(vis[v]||v==fa) continue;
		Get_zx(v,u);
		Size[u]+=Size[v];
		maxn[u]=max(maxn[u],Size[v]);
	}
	maxn[u]=max(maxn[u],sum-Size[u]);
	if(maxn[u]<maxn[rt]) rt=u;
}
void dfs(int u,int fa){
	rev[++num]=u;
	Size[u]=1;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(vis[v]||v==fa) continue;
		dfs(v,u);
		Size[u]+=Size[v];
	}
}

void calc(){
	for(int i=1;i<=num+1;i++) for(int j=0;j<=m;j++) f[i][j]=(i==num+1)?0:-inf;
	for(int i=num;i>=1;i--){
		int u=rev[i],lst=d[u]-1;  //因為一定要選一個，所以在一開始就減掉 
		vector<int> v;
		for(int mi=1;lst>=mi;mi<<=1){
			v.emplace_back(mi);
			lst-=mi;
		} 
		if(lst) v.emplace_back(lst);
		for(int j=0;j<=m;j++) g[j]=(j>=c[u])?(f[i+1][j-c[u]]+w[u]):-inf;  //確保至少選一個 
		for(int x:v) for(int j=m;j>=x*c[u];j--) g[j]=max(g[j],g[j-x*c[u]]+x*w[u]);
		for(int j=0;j<=m;j++){
			f[i][j]=g[j];  //起碼要選一個 
			if(i!=1) f[i][j]=max(f[i][j],f[i+Size[u]][j]);			
		}
	}
	ans=max(ans,f[1][m]);
}
void solve(int t){
	vis[t]=true;
	calc();
	for(int i=head[t];i;i=Next[i]){
		int v=to[i];
		if(vis[v]) continue;
		rt=num=0;
		sum=maxn[rt]=Size[v];
		Get_zx(v,t);
		dfs(rt,0);  
		solve(rt);
	}
}

void Init(){
	tot=ans=0;
	for(int i=1;i<=n;i++) head[i]=vis[i]=0;
}
signed main(){
	int T=read();
	while(T--){
		n=read(),m=read();
		Init();
		
		for(int i=1;i<=n;i++) w[i]=read();	
		for(int i=1;i<=n;i++) c[i]=read();	
		for(int i=1;i<=n;i++) d[i]=read();	
		for(int i=1;i<n;i++){
			int u=read(),v=read();
			add(u,v),add(v,u);
		}
		
		rt=num=0;
		sum=maxn[rt]=n;
		Get_zx(1,0);
		dfs(rt,0);  
		solve(rt); 
		
		printf("%lld\n",ans);
	}
	return 0;
}