文章目錄

• 題目描述
• 解析
• 代碼

題目描述

所謂線段樹維護(hù)dp，就是在線段樹上維護(hù)dp

（逃）

解析

把樹剖一下后就變成了區(qū)間問題
考慮建一棵線段樹，每一個結(jié)點(diǎn)都是一個背包
這樣就能區(qū)間查詢，也能帶修了
這種做法復(fù)雜度其實(shí)并不理想，是logn*dp合并復(fù)雜度
本題背包就是$m^{2}logn$
但是如果出題人想考這個肯定會在數(shù)據(jù)范圍上放你一條生路啦
（調(diào)了半天結(jié)果樹剖掛了就離譜）

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e4+100; const int M=2e6+100; const ll mod=1ll<<31; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,A,B,Q; struct edge{int to,nxt; }p[N<<1]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(edge){y,fi[x]};fi[x]=cnt; } int fa[N],dfn[N],pos[N],low[N],top[N],tim,siz[N],hson[N]; void dfs1(int x,int f){fa[x]=f;siz[x]=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dfs1(to,x);siz[x]+=siz[to];if(!hson[x]||siz[hson[x]]<siz[to]) hson[x]=to;}return; } void dfs2(int x,int tp){top[x]=tp;dfn[++tim]=x;pos[x]=tim;if(hson[x]) dfs2(hson[x],tp);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa[x]||to==hson[x]) continue;dfs2(to,to);} } #define mid ((l+r)>>1) #define ls (k<<1) #define rs (k<<1|1) int T[N][55]; struct bag{ll dp[55];ll mx[55]; }tr[N<<2]; void merge(bag a,bag b,bag &ans){memset(ans.dp,-0x3f,sizeof(ans.dp));memset(ans.mx,-0x3f,sizeof(ans.mx));ans.dp[0]=ans.mx[0]=0;for(int k=1;k<=m;k++){for(int i=0;i<=k;i++) ans.dp[k]=max(ans.dp[k],a.dp[i]+b.dp[k-i]);}for(int k=1;k<=m;k++){ans.mx[k]=max(a.mx[k],b.mx[k]);}return; } void build(int k,int l,int r){if(l==r){for(int i=1;i<=m;i++){tr[k].dp[i]=tr[k].mx[i]=T[dfn[l]][i];}return;}build(ls,l,mid);build(rs,mid+1,r);merge(tr[ls],tr[rs],tr[k]); } void change(int k,int l,int r,int x,bag o){if(l==r){tr[k]=o;return;}if(x<=mid) change(ls,l,mid,x,o);else change(rs,mid+1,r,x,o);merge(tr[ls],tr[rs],tr[k]); } bag ask(int k,int l,int r,int x,int y){ // printf("k=%d l=%d r=%d x=%d y=%d\n",k,l,r,x,y);if(x<=l&&r<=y) return tr[k];if(y<=mid) return ask(ls,l,mid,x,y);else if(x>mid) return ask(rs,mid+1,r,x,y);bag o;merge(ask(ls,l,mid,x,y),ask(rs,mid+1,r,x,y),o);return o; } const int X=1<<16,Y=(1ll<<31)-1; inline int getint(){A=((A^B)+B/X+B*X)&Y;B=((A^B)+A/X+A*X)&Y;return (A^B)%Q; } bag query(int x,int f){bag o;memset(o.dp,0,sizeof(o.dp));memset(o.mx,0,sizeof(o.mx));while(top[x]!=top[f]){merge(o,ask(1,1,n,pos[top[x]],pos[x]),o);x=fa[top[x]];}merge(o,ask(1,1,n,pos[f],pos[x]),o);return o; } int main(){//cout<<X<<" "<<Y;memset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();A=read();B=read();Q=read();for(int i=2;i<=n;i++){int x=read();addline(x,i);}dfs1(1,0);dfs2(1,1); // for(int i=1;i<=n;i++) printf("i=%d fa=%d pos=%d siz=%d hson=%d\n",i,fa[i],pos[i],siz[i],hson[i]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) T[i][j]=getint();sort(T[i]+1,T[i]+1+m);}build(1,1,n);int q=read();for(int o=1;o<=q;o++){int f=read();if(f==0){int p=read();bag now;for(int i=1;i<=m;i++) now.dp[i]=getint();now.dp[0]=0;sort(now.dp+1,now.dp+1+m);for(int i=1;i<=m;i++) now.mx[i]=now.dp[i];change(1,1,n,pos[p],now);}else{int u=read(),v=read();bag ans=ask(1,1,n,pos[u],pos[u]+siz[u]-1);ll res=0;if(u==v) printf("%lld\n",ans.dp[m]);else{bag mx=query(fa[u],v);for(int i=m;i>=0;i--) ans.dp[m]=max(ans.dp[m],ans.dp[i]+mx.mx[m-i]);printf("%lld\n",ans.dp[m]);}}}return 0; } /* */

總結(jié)

以上是生活随笔為你收集整理的YBTOJ：采矿战略（线段树维护dp、树链剖分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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