Description
浩浩荡荡的cg大军发现了一座矿产资源极其丰富的城市，他们打算在这座城市实施新的采矿战略。这个城市可以看成一棵有n个节点的有根树，我们把每个节点用1到n的整数编号。为了方便起见，对于任何一个非根节点v，它任何一个祖先的编号都严格小于v。树上的每个节点表示一个矿点，每条边表示一条街道。作为cg大军的一个小队长，你拥有m个部下。你有一张二维的动态信息表，用Ti,j表示第i行第j列的数据。当你被允许开采某个区域时，你可以将你的部下分配至各个矿点。在第i个矿点安排j个人可以获得Ti,j单位的矿产。允许开采的区域是这样描述的：给你一对矿点(u,v)，保证v是u的祖先（这里定义祖先包括u本身）；u为你控制的区域，可以在以u为根的子树上任意分配部下；u到v的简单路径（不包括u但包括v，若u=v则包括u）为探险路径，在该路径上你可以选择至多一个矿点安排部下。你这次开采的收益为安排有部下的矿点的收益之和。
Solution
对于子树维护一个背包数组, \(f[i]\) 表示取 \(i\) 个的最大收益,链上维护一个 \(max\)
把子树内的合并,链上的不合并,分别维护即可
线段树查询子树,树链剖分查询一下路径 \((x,y)\) 上的点即可
#include<bits/stdc++.h>
#define ls (o<<1)
#define rs (o<<1|1)
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
typedef long long ll;
const int N=20010,M=55;
int n,m,A,B,Q,fa[N],head[N],nxt[N],to[N],num=0,son[N],dep[N];
int sz[N],L[N],R[N],ID=0,top[N],b[N],X=1<<16,Y=(1ll<<31)-1;
struct data{ll f[M];
inline void init(){memset(f,0,sizeof(f));}
}tr[N*4],te[N*4],E,a[N],t0;
inline data operator +(data p,data q){
for(int i=0;i<=m;i++)p.f[i]=max(p.f[i],q.f[i]);
return p;
}
inline data operator *(data p,data q){
data ret;ret.init();
for(int i=0;i<=m;i++)
for(int j=0;i+j<=m;j++)ret.f[i+j]=max(ret.f[i+j],p.f[i]+q.f[j]);
return ret;
}
inline int getint(){
A=((A^B)+B/X+B*X)&Y;
B=((A^B)+A/X+A*X)&Y;
return (A^B)%Q;
}
inline void get(){
for(int i=1;i<=m;i++)E.f[i]=getint();
sort(E.f+1,E.f+m+1);
}
inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
inline void dfs1(int x){
sz[x]=1;
for(int i=head[x],u;i;i=nxt[i]){
if((u=to[i])==fa[x])continue;
dep[u]=dep[x]+1;dfs1(u);sz[x]+=sz[u];
if(sz[u]>sz[son[x]])son[x]=u;
}
}
inline void dfs2(int x,int tp){
b[L[x]=++ID]=x;top[x]=tp;
if(son[x])dfs2(son[x],tp);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x] && to[i]!=son[x])dfs2(to[i],to[i]);
R[x]=ID;
}
inline void upd(int o){tr[o]=tr[ls]+tr[rs],te[o]=te[ls]*te[rs];}
inline void build(int l,int r,int o){
if(l==r){tr[o]=te[o]=a[b[l]];return ;}
int mid=(l+r)>>1;
build(l,mid,ls);build(mid+1,r,rs);
upd(o);
}
inline void mdf(int l,int r,int o,int sa){
if(l==r){tr[o]=te[o]=E;return ;}
int mid=(l+r)>>1;
if(sa<=mid)mdf(l,mid,ls,sa);
else mdf(mid+1,r,rs,sa);
upd(o);
}
inline data qr(int l,int r,int o,int sa,int se){
if(sa<=l && r<=se)return tr[o];
int mid=(l+r)>>1;
if(se<=mid)return qr(l,mid,ls,sa,se);
if(sa>mid)return qr(mid+1,r,rs,sa,se);
return qr(l,mid,ls,sa,mid)+qr(mid+1,r,rs,mid+1,se);
}
inline data qe(int l,int r,int o,int sa,int se){
if(sa<=l && r<=se)return te[o];
int mid=(l+r)>>1;
if(se<=mid)return qe(l,mid,ls,sa,se);
if(sa>mid)return qe(mid+1,r,rs,sa,se);
return qe(l,mid,ls,sa,mid)*qe(mid+1,r,rs,mid+1,se);
}
inline data solve(int x,int y){
data ret;ret.init();
if(x==y)return ret;
x=fa[x];
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret=ret+qr(1,n,1,L[top[x]],L[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ret=ret+qr(1,n,1,L[x],L[y]);
return ret;
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>n>>m>>A>>B>>Q;
for(int i=2;i<=n;i++)gi(fa[i]),link(fa[i],i);
dfs1(1);dfs2(1,1);
for(int i=1;i<=n;i++)get(),a[i]=E;
build(1,n,1);
int C,op,x,y;
cin>>C;
while(C--){
gi(op);gi(x);
if(op==0)get(),mdf(1,n,1,L[x]);
else{
gi(y);
t0=qe(1,n,1,L[x],R[x])*solve(x,y);
printf("%lld\n",t0.f[m]);
}
}
return 0;
}