很厉害的题。在任务计划里躺了一年。。。
题目传送门
思考之路
题目要让我们在付出不超过m的代价在树上找到一个权值最大的连通块。
容易想到树形dp，设\(f_{i,j}\)表示选的连通块中深度最小的点为\(i\)，选的点的代价和为\(j\)的情况下喜爱度的最大值。
那么转移时，对树上的每个点做一次\((max,+)\)卷积。这里的\((max,+)\)卷积与一般的树形背包复杂度不同，一般的树形背包枚举时要对子树大小\(siz\)取\(min\)，通过均摊可以证明总复杂度是\(O(nm)\)的，但这里第二维不再是点数，需要把整个值域都枚举一遍，因此一次\((max,+)\)卷积复杂度无可避免是\(O(m^2)\)的，总复杂度是\(O(nm^2)\)的,十分不优秀。
复杂度瓶颈在于\((max,+)\)卷积的\(O(m^2)\)，而且该形式的卷积没有什么好的优化方式，我们要想办法避免\((max,+)\)卷积
有一个可以用来解决树上连通块问题的套路：树上依赖型背包
我们先来回想普通的背包是如何做的：每次加入一个新的物品，然后\(O(m)\)累计这个物品的贡献。
而普通的树上背包则是采用了\((max,+)\)卷积合并两个背包的情况，普通的树上背包通过均摊贡献可以证明复杂度是优秀的，但是在这道题目中，合并背包则需要\(O(m^2)\)的复杂度，我们考虑把合并背包改为每次插入一个点，在插入的过程中要满足与根连通的条件。
我们求出这棵树的\(dfn\)序，那么每颗子树都恰好对应一段区间，我们按照\(dfn\)序从小到大dp：
设\(f_{i,j}\)表示在所有\(dfn<i\)的点中选取总代价为\(j\)的点集，满足这个点集是与根相连的一个连通块，且\(dfn\)序为\(i\)的点与该点集连通的最大价值。
转移分两种情况讨论：若选\(i\)，把\(i\)插入到点集中，用单调队列优化多重背包的手法累计\(i\)的贡献到\(f_{i+1}\)中（即对应位取\(max\)）；若不选\(i\)，那么\(i\)的子树都不能选，把贡献累积到\(f_{i+siz_i}\)中（对应位取\(max\)）
这样对于一个选定的根，dp的总复杂度为\(O(nm)\),但是为了找到所有情况，需要每个点都当做根，进行一次dp，总复杂度\(O(n^2m)\)。
不难发现，考虑过包含1的情况，剩下不包含1的情况，这样必须在1的若干个儿子的子树中选取连通块，这就变成了一个子问题，递归下去，用点分治限制层数，达到\(O(nm\log n)\)。这里点分治不再是统计路径，而是统计连通块。
有个细节是要把dp数组的初始值设为-inf,因为与普通的背包不同，普通的背包没有额外的限制条件，任意一种状态都能达到，而这里的树上依赖型背包，需要满足与根节点连通的条件，有些状态是永远无法达到的，应该设为-inf.
Code
#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define lb long double
inline int rd(){
register int x=0,w=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') {ch=getchar(); w=-1;}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();}
return x*w;
}
const int N=505,M=4005,inf=1e9;
int t,n,m,w[N],c[N],d[N];
int ans;
vector<int>v[N];
int siz[N],maxn[N],vis[N],q[M],l,r,tot,f[N][M],id[N];
void dfssiz(int x,int fa)
{
siz[x]=1;
for(int i=0;i<v[x].size();++i)
{
int y=v[x][i];if(vis[y]||y==fa) continue;
dfssiz(y,x);siz[x]+=siz[y];
}
}
void dfsht(int x,int S,int fa,int &rt)
{
maxn[x]=S-siz[x];
for(int i=0;i<v[x].size();++i)
{
int y=v[x][i];if(vis[y]||y==fa) continue;
dfsht(y,S,x,rt);maxn[x]=max(maxn[x],siz[y]);
}
if(maxn[x]<maxn[rt]) rt=x;
}
void dfs(int x,int fa)
{
siz[x]=1;id[++tot]=x;
for(int i=0;i<v[x].size();++i){
int y=v[x][i];if(y==fa||vis[y]) continue;
dfs(y,x);siz[x]+=siz[y];
}
}
void work(int x)
{
dfssiz(x,0);
int rt=0;
dfsht(x,siz[x],0,rt);
tot=0;
dfs(rt,0);vis[rt]=1;
for(int i=1;i<=tot+1;++i) memset(f[i],0xcf,sizeof f[i]);
// for(int i=2;i<=tot+1;++i) f[i][0]=-inf*2;
f[1][0]=0;
for(int i=1;i<=tot;++i)
{
for(int u=0;u<c[id[i]];++u)
{
q[l=r=1]=u;
for(int v=1;v*c[id[i]]+u<=m;++v)
{
int cur=v*c[id[i]]+u;
if((cur-q[l])/c[id[i]]>d[id[i]]) l++;
f[i+1][cur]=max(f[i+1][cur],f[i][q[l]]+(cur-q[l])/c[id[i]]*w[id[i]]);
while(l<=r&&(f[i][q[r]]-q[r]/c[id[i]]*w[id[i]])<=(f[i][cur]-cur/c[id[i]]*w[id[i]])) r--;
q[++r]=cur;
}
}
for(int j=1;j<=m;++j) f[i+siz[id[i]]][j]=max(f[i+siz[id[i]]][j],f[i][j]);
}
for(int i=0;i<=m;++i)
ans=max(ans,f[tot+1][i]);
for(int i=0;i<v[rt].size();++i)
{
int y=v[rt][i];if(vis[y]) continue;
work(y);
}
}
signed main()
{
// freopen("P6326_2.in","r",stdin);
// freopen("my.out","w",stdout);
maxn[0]=1e9;
t=rd();
while(t--)
{
n=rd();m=rd();
for(int i=1;i<=n;++i) w[i]=rd();
for(int i=1;i<=n;++i) c[i]=rd();
for(int i=1;i<=n;++i) d[i]=rd();
for(int i=1;i<n;++i)
{
int x=rd(),y=rd();
v[x].push_back(y);v[y].push_back(x);
}
ans=0;
work(1);
cout<<ans<<'\n';
for(int i=1;i<=n;++i) v[i].clear(),vis[i]=0;
}
return 0;
}