记录编号	141598	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]采矿	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.404 s
提交时间	2014-12-03 14:37:38	内存使用	25.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=20010,SIZEM=51;
int N,M;//N个节点,M个人
int fa[SIZEN]={0};//每个节点的父亲
vector<int> c[SIZEN];//每个节点的儿子
class TABLE{//选0~M个人的最优值
public:
	int s[SIZEM];
}zero_table;
TABLE add(TABLE a,TABLE b,bool typ){//typ=0是选一个,typ=1是叠加选
	TABLE c;
	for(int i=0;i<=M;i++){
		c.s[i]=0;
		if(!typ) c.s[i]=max(a.s[i],b.s[i]);
		else for(int j=0;j<=i;j++) c.s[i]=max(c.s[i],a.s[j]+b.s[i-j]);
	}
	return c;
}
class GENERATOR{//数据生成器
public:
	int A,B,Q;
	int getint(void){
		A=((A^B)+(B>>16)+(B<<16))&0x7fffffff;
		B=((A^B)+(A>>16)+(A<<16))&0x7fffffff;
		return(A^B)%Q;
	}
	TABLE gettab(void){
		TABLE T;
		T.s[0]=0;
		for(int i=1;i<=M;i++) T.s[i]=getint();
		sort(T.s,T.s+M+1);
		return T;
	}
}GRT;
class NODE{//线段树的节点
public:
	int a,b;//范围a~b
	int l,r;//两个儿子
	TABLE t;//范围内的表
	#define a(x) Tree[x].a
	#define b(x) Tree[x].b
	#define l(x) Tree[x].l
	#define r(x) Tree[x].r
	#define t(x) Tree[x].t
};
NODE Tree[SIZEN*4];
int tot=0;
void update(int now,bool typ){
	if(!now) return;
	if(!l(now)) return;
	t(now)=add(t(l(now)),t(r(now)),typ);
}
int build(int x,int y,bool typ,TABLE lis[]){
	int p=++tot;
	a(p)=x,b(p)=y;
	if(x==y){
		l(p)=r(p)=0;
		t(p)=lis[x];
	}
	else{
		int mid=(x+y)>>1;
		l(p)=build(x,mid,typ,lis);
		r(p)=build(mid+1,y,typ,lis);
		update(p,typ);
	}
	return p;
}
TABLE query(int now,int x,int y,bool typ){
	if(!now) return zero_table;
	if(a(now)>y||b(now)<x) return zero_table;
	if(a(now)>=x&&b(now)<=y) return t(now);
	return add(query(l(now),x,y,typ),query(r(now),x,y,typ),typ);
}
void change(int now,int x,TABLE &nt,bool typ){
	if(!now) return;
	if(a(now)>x||b(now)<x) return;
	if(a(now)==x&&b(now)==x) t(now)=nt;
	else{
		change(l(now),x,nt,typ);
		change(r(now),x,nt,typ);
		update(now,typ);
	}
}
int depth[SIZEN]={0};
int height[SIZEN]={0};
int belong[SIZEN]={0};
int top[SIZEN]={0};
int dfn[SIZEN]={0};
int dfslis[SIZEN]={0};
int sonsz[SIZEN]={0};
int tim=0;
void DFS(int x){//DFS一遍,建出DFS序列同时树链剖分
	tim++;
	dfn[x]=tim;dfslis[tim]=x;
	height[x]=0;sonsz[x]=1;belong[x]=x;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		depth[u]=depth[x]+1;
		DFS(u);
		sonsz[x]+=sonsz[u];
		if(height[u]+1>height[x]){
			height[x]=height[u]+1;
			belong[x]=belong[u];
		}
	}
}
TABLE T[SIZEN];
TABLE tblis[SIZEN];
int lisroot;
int chainroot[SIZEN]={0};
void prepare_chain(int x){
	top[x]=x;
	tblis[depth[x]]=T[x];
	while(belong[fa[top[x]]]==x){
		top[x]=fa[top[x]];
		tblis[depth[top[x]]]=T[top[x]];
	}
	chainroot[x]=build(depth[top[x]],depth[x],0,tblis);
}
void prepare(void){
	for(int i=1;i<=N;i++) T[i]=GRT.gettab();
	for(int i=1;i<=N;i++) tblis[dfn[i]]=T[i];
	lisroot=build(1,N,1,tblis);
	for(int i=1;i<=N;i++) if(belong[i]==i) prepare_chain(i);
}
void modify(int x){
	T[x]=GRT.gettab();
	change(lisroot,dfn[x],T[x],1);
	change(chainroot[belong[x]],depth[x],T[x],0);
}
int ask(int u,int v){//v是u的祖先
	static TABLE anst,ansc;
	anst=query(lisroot,dfn[u],dfn[u]+sonsz[u]-1,1);
	if(u==v) return anst.s[M];
	ansc=zero_table;
	u=fa[u];
	while(true){
		int k=belong[u];
		ansc=add(ansc,query(chainroot[k],max(depth[top[k]],depth[v]),depth[u],0),0);
		if(depth[fa[top[k]]]>=depth[v]) u=fa[top[k]];
		else break;
	}
	anst=add(ansc,anst,1);
	return anst.s[M];
}
void work(void){
	int C,cmd,u,v;
	scanf("%d",&C);
	for(int i=1;i<=C;i++){
		scanf("%d",&cmd);
		if(!cmd){
			scanf("%d",&u);
			modify(u);
		}
		else{
			scanf("%d%d",&u,&v);
			printf("%d\n",ask(u,v));
		}
	}
}
void read(void){
	depth[1]=1;
	memset(zero_table.s,0,sizeof(zero_table.s[0])*SIZEM);
	scanf("%d%d%d%d%d",&N,&M,&GRT.A,&GRT.B,&GRT.Q);
	for(int i=2;i<=N;i++){
		scanf("%d",&fa[i]);
		c[fa[i]].push_back(i);
	}
}
int main(){
	freopen("mine.in","r",stdin);
	freopen("mine.out","w",stdout);
	read();
	DFS(1);
	prepare();
	work();
	return 0;
}