P6326 Shopping
题意等价于要买一个连通块。
首先如果我们能求出一个 dp 数组：
\(f_{i,j}\) 表示 \(i\) 子树内，有 \(j\) 元，一定要选 \(i\)，能得到的最大价值。
那么 \(f_{1,m}\) 就是一定选根的答案。
然后点分治即可。
接下来就是怎么在合理的复杂度内求出 dp 数组。
直接背包显然不行，因为这不是一个普通的树形背包，他的第二维跟子树大小无关，所以合并子树的复杂度是单次 \(O(m^2)\)，总复杂度是 \(O(nm^2)\)。
然后就诞生了一种很厉害的科技——树上依赖性背包。
因为选儿子就一定要选父亲，所以管他叫这个名字。
具体做法是：
设 \(f_{i,j}\) 表示考虑 dfn 位于 \([i,n]\) 中的点，有 \(j\) 元钱能得到的最大价值。
下面设根为 \(1\)。
因为根是 dfn 最小的点，它一定要选，特判一下。
接下来考虑 \(dfn=2\) 的点，不妨设为 \(2\)，他一定是 \(1\) 的儿子，他有两种选择：
- 不选，那他子树内的点都不能选，而众所周知，子树内的点的 dfn 是连续的一段区间，那么转移就是：\(f_{2 + Size_2,j} \to f_{2,j}\)。
此时剩下的问题相当是把 \(2\) 这棵子树去掉了，仍然是一棵树，并且 dfn 也是一个后缀。
并且如果在剩下的这棵树内选择了一个连通块，那么放到原树内选出的也是一个连通块。
所以他是一个子问题。 - 选，转移是：\(max_{1\le k \le d_2}(f_{3,j-c_2\times k} + w_2\times k) \to f_{2,j}\)。
这个转移本质是多重背包，可以用二进制拆分优化到 \(O(\log d)\)，也可以用单调队列优化到均摊 \(O(1)\)。
此时 \(1,2\) 构成了一个连通块，我们把它视为新的根，原本 \(1,2\) 的子树接到这个新的根上。
那么构成的仍然是一棵树，dfn 是一个后缀，且如果在这棵新树里选出了一个连通块，那么放到原树上也是一个连通块。
所以它也是一个子问题。
然后把新的根当根继续考虑 \(dfn=3\) 的点。
答案是 \(f_{1,m}\)。
这个 dp 是 \(O(nm\log d)\) 或者 \(O(nm)\) 的。
总复杂度乘一个点分治的 \(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;
}