网站建设免费发布,百度怎么网站排名,精准营销的主要价值,python适合大型网站开发吗文章目录题目描述解析代码题目描述 所谓线段树维护dp#xff0c;就是在线段树上维护dp #xff08;逃#xff09;
解析
把树剖一下后就变成了区间问题 考虑建一棵线段树#xff0c;每一个结点都是一个背包 这样就能区间查询#xff0c;也能带修了 这种做法复杂度其实并不…
文章目录题目描述解析代码题目描述 所谓线段树维护dp就是在线段树上维护dp 逃
解析
把树剖一下后就变成了区间问题 考虑建一棵线段树每一个结点都是一个背包 这样就能区间查询也能带修了 这种做法复杂度其实并不理想是logn*dp合并复杂度 本题背包就是m2lognm^2lognm2logn 但是如果出题人想考这个肯定会在数据范围上放你一条生路啦 调了半天结果树剖挂了就离谱
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e4100;
const int M2e6100;
const ll mod1ll31;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}
int n,m,A,B,Q;
struct edge{int to,nxt;
}p[N1];
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 ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) 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 ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa[x]||tohson[x]) continue;dfs2(to,to);}
}
#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
int T[N][55];
struct bag{ll dp[55];ll mx[55];
}tr[N2];
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 k1;km;k){for(int i0;ik;i) ans.dp[k]max(ans.dp[k],a.dp[i]b.dp[k-i]);}for(int k1;km;k){ans.mx[k]max(a.mx[k],b.mx[k]);}return;
}
void build(int k,int l,int r){if(lr){for(int i1;im;i){tr[k].dp[i]tr[k].mx[i]T[dfn[l]][i];}return;}build(ls,l,mid);build(rs,mid1,r);merge(tr[ls],tr[rs],tr[k]);
}
void change(int k,int l,int r,int x,bag o){if(lr){tr[k]o;return;}if(xmid) change(ls,l,mid,x,o);else change(rs,mid1,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(xlry) return tr[k];if(ymid) return ask(ls,l,mid,x,y);else if(xmid) return ask(rs,mid1,r,x,y);bag o;merge(ask(ls,l,mid,x,y),ask(rs,mid1,r,x,y),o);return o;
}
const int X116,Y(1ll31)-1;
inline int getint(){A((A^B)B/XB*X)Y;B((A^B)A/XA*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);xfa[top[x]];}merge(o,ask(1,1,n,pos[f],pos[x]),o);return o;
}
int main(){//coutX Y;memset(fi,-1,sizeof(fi));cnt-1;nread();mread();Aread();Bread();Qread();for(int i2;in;i){int xread();addline(x,i);}dfs1(1,0);dfs2(1,1);
// for(int i1;in;i) printf(i%d fa%d pos%d siz%d hson%d\n,i,fa[i],pos[i],siz[i],hson[i]);for(int i1;in;i){for(int j1;jm;j) T[i][j]getint();sort(T[i]1,T[i]1m);}build(1,1,n);int qread();for(int o1;oq;o){int fread();if(f0){int pread();bag now;for(int i1;im;i) now.dp[i]getint();now.dp[0]0;sort(now.dp1,now.dp1m);for(int i1;im;i) now.mx[i]now.dp[i];change(1,1,n,pos[p],now);}else{int uread(),vread();bag ansask(1,1,n,pos[u],pos[u]siz[u]-1);ll res0;if(uv) printf(%lld\n,ans.dp[m]);else{bag mxquery(fa[u],v);for(int im;i0;i--) ans.dp[m]max(ans.dp[m],ans.dp[i]mx.mx[m-i]);printf(%lld\n,ans.dp[m]);}}}return 0;
}
/*
*/
