记录编号 |
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;
}