description

權(quán)限題。
樹上\(n\)個節(jié)點每個節(jié)點都有一種物品，每種物品有其價值，價格，數(shù)量，只能買一個連通塊中的物品，求\(m\)元能買到物品價值的最大值。

data range

\[ n\le 500,m\le 4000,T\le 5,c_i\le m\]

solution

緊跟\(YCB\)聚聚的步伐

首先可以想到以每個點為根做樹形依賴背包

樹形依賴背包

設\(f[i][j]\)表示在子樹\(i\)中買了價值為\(j\)的物品

如果直接對父親轉(zhuǎn)移是每次\(O(nc^2)\)的

我們把每個連通塊考慮成一條路徑，如果選某個點就前往這個點\(dfn\)序的下一個點，
如果不選就跳過整棵子樹做轉(zhuǎn)移

這樣做再加上多重背包的單調(diào)隊列優(yōu)化可以達到每次\(O(nc)\)

總復雜度為\(O(n^2c)\)

然后套一下點分治或者\(dsu\ on\ tree\)都可以

code

#include<bits/stdc++.h> #include<algorithm> #include<iostream> #include<cstdlib> #include<iomanip> #include<cstring> #include<complex> #include<vector> #include<cstdio> #include<string> #include<bitset> #include<ctime> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #define FILE "a" #define mp make_pair #define pb push_back #define RG register #define il inline using namespace std; typedef unsigned long long ull; typedef vector<int>VI; typedef long long ll; typedef double dd; const dd eps=1e-10; const int mod=1e9+7; const int N=510; const int M=4010; const dd pi=acos(-1); const int inf=mod; const ll INF=1e18+1; const ll P=100000; il ll read(){RG ll data=0,w=1;RG char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();return data*w; }il void file(){srand(time(NULL)+rand());freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout); }int n,m,w[N],c[N],d[N],ans; int head[N],nxt[N<<1],to[N<<1],cnt; int sz[N],son[N],dfn[N],fw[N],cntw; void dfs1(int u,int fa){sz[u]=1;son[u]=0;for(RG int i=head[u];i;i=nxt[i]){RG int v=to[i];if(v==fa)continue;dfs1(v,u);sz[u]+=sz[v];if(sz[son[u]]<sz[v])son[u]=v;} } void dfs2(int u,int fa){dfn[u]=++cntw;fw[cntw]=u;for(RG int i=head[u];i;i=nxt[i]){RG int v=to[i];if(v==fa||v==son[u])continue;dfs2(v,u);}if(son[u])dfs2(son[u],u); }int dp[N][M],q[M],l,r; il void upd(int &a,int b){a=a>b?a:b;} il void work(int *f1,int *f2,int u){for(RG int i=0,ret;i<c[u];i++){l=1;r=0;for(RG int j=0;j*c[u]+i<=m;j++){while(l<=r&&j-q[l]>d[u])l++;ret=l>r?-inf:f2[q[l]*c[u]+i]+(j-q[l])*w[u];upd(f1[j*c[u]+i],ret);while(l<=r&&f2[q[r]*c[u]+i]<=f2[j*c[u]+i]+(q[r]-j)*w[u])r--;q[++r]=j;}} }void dsu(int u,int fa,int k){for(RG int i=head[u];i;i=nxt[i]){RG int v=to[i];if(v==fa||v==son[u])continue;dsu(v,u,0);}if(son[u])dsu(son[u],u,1);for(RG int i=0;i<=m;i++)dp[fw[dfn[u]+sz[u]]][i]=-inf;dp[fw[dfn[u]+sz[u]]][0]=0;for(RG int i=dfn[u]+sz[u]-sz[son[u]]-1;i>=dfn[u];i--){RG int x=fw[i];for(RG int j=0;j<=m;j++)dp[x][j]=-inf;if(x!=u)for(RG int j=0;j<=m;j++)upd(dp[x][j],dp[fw[i+sz[x]]][j]);work(dp[x],dp[fw[i+1]],x);}for(RG int i=0;i<=m;i++)upd(ans,dp[u][i]);if(k){for(RG int i=0;i<=m;i++)dp[u][i]=-inf;for(RG int i=0;i<=m;i++)upd(dp[u][i],dp[fw[dfn[u]+sz[u]]][i]);work(dp[u],dp[fw[dfn[u]+1]],u);} }int main() {RG int T=read();while(T--){n=read();m=read();ans=-inf;fw[n+1]=n+1;cnt=cntw=0;memset(head,0,sizeof(head));for(RG int i=1;i<=n;i++)w[i]=read();for(RG int i=1;i<=n;i++)c[i]=read();for(RG int i=1;i<=n;i++)d[i]=read();for(RG int i=1,u,v;i<n;i++){u=read();v=read();to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;} dfs1(1,0);dfs2(1,0);dsu(1,0,0); printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cjfdf/p/9540057.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ4182]Shopping的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。