烟台的网站建设,网站建设需要几个人,阀门专业网站建设,建设本地网站description 权限题。 树上\(n\)个节点每个节点都有一种物品#xff0c;每种物品有其价值#xff0c;价格#xff0c;数量#xff0c;只能买一个连通块中的物品#xff0c;求\(m\)元能买到物品价值的最大值。 data range \[ n\le 500,m\le 4000,T\le 5,c_i\le m\] solutio…description 权限题。 树上\(n\)个节点每个节点都有一种物品每种物品有其价值价格数量只能买一个连通块中的物品求\(m\)元能买到物品价值的最大值。 data range \[ n\le 500,m\le 4000,T\le 5,c_i\le m\] solution 紧跟\(YCB\)聚聚的步伐 首先可以想到以每个点为根做树形依赖背包 树形依赖背包 设\(f[i][j]\)表示在子树\(i\)中买了价值为\(j\)的物品 如果直接对父亲转移是每次\(O(nc^2)\)的 我们把每个连通块考虑成一条路径如果选某个点就前往这个点\(dfn\)序的下一个点 如果不选就跳过整棵子树做转移 这样做再加上多重背包的单调队列优化可以达到每次\(O(nc)\) 总复杂度为\(O(n^2c)\) 然后套一下点分治或者\(dsu\ on\ tree\)都可以 code #includebits/stdc.h
#includealgorithm
#includeiostream
#includecstdlib
#includeiomanip
#includecstring
#includecomplex
#includevector
#includecstdio
#includestring
#includebitset
#includectime
#includecmath
#includequeue
#includestack
#includemap
#includeset
#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 vectorintVI;
typedef long long ll;
typedef double dd;
const dd eps1e-10;
const int mod1e97;
const int N510;
const int M4010;
const dd piacos(-1);
const int infmod;
const ll INF1e181;
const ll P100000;
il ll read(){RG ll data0,w1;RG char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();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[N1],to[N1],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 ihead[u];i;inxt[i]){RG int vto[i];if(vfa)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 ihead[u];i;inxt[i]){RG int vto[i];if(vfa||vson[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){aab?a:b;}
il void work(int *f1,int *f2,int u){for(RG int i0,ret;ic[u];i){l1;r0;for(RG int j0;j*c[u]im;j){while(lrj-q[l]d[u])l;retlr?-inf:f2[q[l]*c[u]i](j-q[l])*w[u];upd(f1[j*c[u]i],ret);while(lrf2[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 ihead[u];i;inxt[i]){RG int vto[i];if(vfa||vson[u])continue;dsu(v,u,0);}if(son[u])dsu(son[u],u,1);for(RG int i0;im;i)dp[fw[dfn[u]sz[u]]][i]-inf;dp[fw[dfn[u]sz[u]]][0]0;for(RG int idfn[u]sz[u]-sz[son[u]]-1;idfn[u];i--){RG int xfw[i];for(RG int j0;jm;j)dp[x][j]-inf;if(x!u)for(RG int j0;jm;j)upd(dp[x][j],dp[fw[isz[x]]][j]);work(dp[x],dp[fw[i1]],x);}for(RG int i0;im;i)upd(ans,dp[u][i]);if(k){for(RG int i0;im;i)dp[u][i]-inf;for(RG int i0;im;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 Tread();while(T--){nread();mread();ans-inf;fw[n1]n1;cntcntw0;memset(head,0,sizeof(head));for(RG int i1;in;i)w[i]read();for(RG int i1;in;i)c[i]read();for(RG int i1;in;i)d[i]read();for(RG int i1,u,v;in;i){uread();vread();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;
}转载于:https://www.cnblogs.com/cjfdf/p/9540057.html
