[国家集训队2011]采矿 - mikumikumi - 236418

记录编号	236418	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]采矿	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	6.267 s
提交时间	2016-03-14 08:06:44	内存使用	70.58 MiB
显示代码纯文本
#include<cstdio>
#include<deque>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEM=60,SIZEN=20010;
typedef long long LL;
int N,M,A,B,Q;
class miku
{
public:
	int l,r;
	int s[SIZEM];
	int mx[SIZEM];//在这个区间内T[i][j]的最大值
	int id[SIZEM];
	void print()
	{
		for(int i=1;i<=M;i++) cout<<s[i]<<" "<<mx[i]<<" "<<id[i]<<endl;
	}
}tr[SIZEN*4];
int top[SIZEN],w[SIZEN],siz[SIZEN],dep[SIZEN],f[SIZEN],pos[SIZEN];
int son[SIZEN];//重儿子
int totw,tot;
deque<int> c[SIZEN];
int X=(1<<16),Y=(1<<31)-1;
void add(int fr,int to){c[fr].push_back(to);}
void read()
{
	scanf("%d%d%d%d%d",&N,&M,&A,&B,&Q);
	f[1]=0;
	for(int i=1;i<N;i++)
	{
		scanf("%d",&f[i+1]);
		add(f[i+1],i+1);
	}
}
void dfs(int x)//树链剖分
{
	dep[x]=dep[f[x]]+1;siz[x]=1;son[x]=0;
	for(int i=0;i<c[x].size();i++)
	{
		int v=c[x][i];
		dfs(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]]) son[x]=v;
	}
}
void maketree(int x,int tp)
{
	pos[x]=++totw;top[x]=tp;
	if(son[x]) maketree(son[x],tp);
	for(int i=0;i<c[x].size();i++)
	{
		int v=c[x][i];
		if(v==son[x]) continue;
		maketree(v,v);
	}
}
int T[SIZEN][SIZEM]={0};
int GetInt()
{
	A=((A^B)+(B/X)+(B*X))&Y;
	B=((A^B)+(A/X)+(A*X))&Y;
	return (A^B)%Q;
}
void make(int root,int k)
{
	T[k][0]=0;
	for(int i=1;i<=M;i++) T[k][i]=GetInt();
	sort(T[k]+1,T[k]+M+1);
	for(int i=1;i<=M;i++) tr[root].mx[i]=tr[root].s[i]=T[k][i],tr[root].id[i]=k;
}
void update(int root)
{
	for(int i=0;i<=M;i++)
	{
		tr[root].s[i]=0;
		for(int j=0;j<=i;j++) tr[root].s[i]=max(tr[root*2].s[j]+tr[root*2+1].s[i-j],tr[root].s[i]);
		if(tr[root*2].mx[i]>tr[root*2+1].mx[i]) tr[root].mx[i]=tr[root*2].mx[i],tr[root].id[i]=tr[root*2].id[i];
		else tr[root].mx[i]=tr[root*2+1].mx[i],tr[root].id[i]=tr[root*2+1].id[i];
	}
}
void seg_built(int root,int l,int r,int k)
{
	if(r<k||l>k) return ;
	if(l==r)
	{
		make(root,k);
		return;
	}
	int mid=(l+r)/2;
	seg_built(root*2,l,mid,k);
	seg_built(root*2+1,mid+1,r,k);
	update(root);
}
void prepare()
{
	dfs(1);
	maketree(1,1);
	for(int i=1;i<=N;i++) seg_built(1,1,totw,pos[i]);
}
class poi//临时的类
{
	public:
	//要不是为了减小常数我才不这样写呢
	int s[SIZEM];
	poi()
	{
		memset(s,0,sizeof(s));
	}
	void add(poi a,poi b)
	{
		memset(s,0,sizeof(s));
		for(int i=0;i<=M;i++)
		{
			for(int j=0
				;j<=i;j++)
			{
				s[i]=max(s[i],a.s[j]+b.s[i-j]);
			}
		}
	}
}zero;
poi get(int root,int lo,int hi,int l,int r)
{
	if(hi<l||lo>r) return zero;
	if(l<=lo&&hi<=r){
		poi A;
		for(int i=0;i<=M;i++) A.s[i]=tr[root].s[i];
		return A;
	}
	
	int mid=(lo+hi)/2;
	poi A;
	A.add(get(root*2,lo,mid,l,r),get(root*2+1,mid+1,hi,l,r));
	return A;
}
int getmx(int root,int lo,int hi,int l,int r,int cnt)
{
	if(hi<l||lo>r) return 0;
	if(l<=lo&&hi<=r)
	{
		return tr[root].mx[cnt];
	}
	int re=0;
	int mid=(lo+hi)/2;
	re=max(getmx(root*2,lo,mid,l,r,cnt),getmx(root*2+1,mid+1,hi,l,r,cnt));
	return re;
}
int now=0;
int find(int u,int v,int cnt)
{
	int tem=0;
	int f1=top[u],f2=top[v];
	while(f1!=f2)
	{
		if(dep[f1]<dep[f2])
		{
			swap(f1,f2),swap(u,v);
		}
		tem=max(tem,getmx(1,1,totw,pos[f1],pos[u],cnt));
		u=f[f1];f1=top[u];
	}
	if(dep[u]>dep[v]) swap(u,v);
	tem=max(tem,getmx(1,1,totw,pos[u],pos[v],cnt));
	return tem;
}
void calc(int u,int v)
{
	poi
	ans1;
	ans1=get(1,1,totw,pos[u],pos[u]+siz[u]-1);
	int ans2[SIZEM]={0};
	if(u!=v)
	{
		u=f[u];
		for(int i=1;i<=M;i++) ans2[i]=find(u,v,i);
	}
	int ans=0;
	for(int i=0;i<=M;i++) ans=max(ans,ans1.s[i]+ans2[M-i]);
	printf("%d\n",ans);
}
void work()
{
	int C;
	scanf("%d",&C);
	int cmd;
	int u,v;
	for(int i=1;i<=C;i++)
	{
		scanf("%d",&cmd);
		if(!cmd)
		{
			scanf("%d",&u);
			seg_built(1,1,totw,pos[u]);
		}
		else
		{
			now++;
			scanf("%d%d",&u,&v);
			calc(u,v);
		}
	}
}
int main()
{
	freopen("mine.in","r",stdin);
	freopen("mine.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}