bzoj4182/luoguP6326 Shopping(点分治，树上背包)

bzoj4182/luoguP6326 Shopping(点分治，树上背包)

bzoj它爆炸了。

luogu

题解时间

如果直接暴力背包，转移复杂度是 $ m^{2} $ 。

考虑改成点分治。

那么问题来了点分治有什么优点呢？

每次从分治中心开始搜索进行dp，保证从根到当前点都被购买至少一件。

这样复杂度就会被压成 $ O(nm \log n \ max d) $ 。

加个二进制分组变成 $ O(nm \log n \log d) $ 。

也可以用dfs序+单调队列变成 $ O(nm \log n) $ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};
template<typename TP>inline void read(TP &tar)
{
	TP ret=0,f=1;char ch=getchar();
	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
	while(ch>=‘0‘&&ch<=‘9‘){ret=ret*10+(ch-‘0‘);ch=getchar();}
	tar=ret*f;
}
template<typename TP,typename... Args>inline void read(TP& t,Args&... args){read(t),read(args...);}
namespace RKK
{
const int N=511,M=4011;
void cmax(int &a,const int &b){a=max(a,b);}
struct sumireko{int to,ne;}e[N<<1];int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
int n,m,w[N],c[N],d[N],ans;
int size[N],ms,rt;bool vis[N];
void getrt(int x,int f)
{
	size[x]=1;int ma=0;for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(!vis[t]&&t!=f)
		getrt(t,x),size[x]+=size[t],ma=max(ma,size[t]);
	if(max(ma,ms-size[x])*2<=ms) rt=x;
}
int dp[N][M];
void dfs(int x,int f,int lim)
{
	if(lim<=0) return;int l=d[x];
	for(int i=1;i<l;l-=i,i<<=1)
		for(int k=lim;k>=i*c[x];k--) cmax(dp[x][k],dp[x][k-i*c[x]]+i*w[x]);
	for(int k=lim;k>=l*c[x];k--) cmax(dp[x][k],dp[x][k-l*c[x]]+l*w[x]);
	for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(!vis[t]&&t!=f)
	{
		for(int k=0;k+c[t]<=lim;k++) dp[t][k]=dp[x][k]+w[t];
		dfs(t,x,lim-c[t]);
		for(int k=0;k+c[t]<=lim;k++) cmax(dp[x][k+c[t]],dp[t][k]);
	}
}
void FD(int x,int msn)
{
	ms=msn,getrt(x,0),vis[rt]=1,x=rt;
	for(int i=0;i+c[x]<=m;i++) dp[x][i]=w[x];
	dfs(x,0,m-c[x]);
	for(int i=0;i+c[x]<=m;i++) cmax(ans,dp[x][i]);
	for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(!vis[t])
		FD(t,size[t]<size[x]?size[t]:msn-size[x]);
}
void BFD()
{
	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]),d[i]--;
	for(int i=2,x,y;i<=n;i++) read(x,y),addline(x,y),addline(y,x);
	FD(1,n);printf("%d\n",ans);
}
void ESM()
{
	memset(he,0,sizeof(he)),ecnt=0;
	memset(vis,0,sizeof(vis));
	ans=0;
}
int main()
{
	static int TAT;read(TAT);while(TAT--) BFD(),ESM();
	return 0;
}
}
int main(){return RKK::main();}

bzoj4182/luoguP6326 Shopping(点分治，树上背包)

原文：https://www.cnblogs.com/rikurika/p/13205108.html