记录编号	385148	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]奈特	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.057 s
提交时间	2017-03-20 12:25:11	内存使用	70.10 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct edge{
  int to,next;
}lst[maxn<<1];int first[maxn],len=1;
void addedge(int a,int b){
  lst[len].to=b;lst[len].next=first[a];first[a]=len++;
}
int n,root;
int prt[maxn],sz[maxn],top[maxn],depth[maxn],hvy[maxn],dfn[maxn],T;
void dfs1(int x){
  sz[x]=1;
  for(int pt=first[x];pt;pt=lst[pt].next){
    depth[lst[pt].to]=depth[x]+1;
    dfs1(lst[pt].to);
    sz[x]+=sz[lst[pt].to];
    if(sz[lst[pt].to]>sz[hvy[x]])hvy[x]=lst[pt].to;
  }
}
void dfs2(int x){
  dfn[x]=++T;
  if(hvy[x]){
    top[hvy[x]]=top[x];dfs2(hvy[x]);
    for(int pt=first[x];pt;pt=lst[pt].next){
      if(lst[pt].to==hvy[x])continue;
      top[lst[pt].to]=lst[pt].to;
      dfs2(lst[pt].to);
    }
  }
}
struct node{
  node* ch[2];int sum;
  node(){}
  node(int x){sum=x;ch[0]=ch[1]=0;}
}t[maxn*50];int trsz=0;
node* newnode(int x){
  t[++trsz]=node(x);return t+trsz;
}
node* Root[maxn];
void Insert(node* rt0,node* &rt,int l,int r,int k){
  rt=newnode(rt0->sum+1);
  if(l==r)return;
  int mid=(l+r)>>1;
  if(k<=mid){
    Insert(rt0->ch[0],rt->ch[0],l,mid,k);
    rt->ch[1]=rt0->ch[1];
  }else{
    Insert(rt0->ch[1],rt->ch[1],mid+1,r,k);
    rt->ch[0]=rt0->ch[0];
  }
}
int qsum(node* rt,int l,int r,int ql,int qr){
  if(ql<=l&&r<=qr)return rt->sum;
  int mid=(l+r)>>1,ans=0;
  if(ql<=mid)ans+=qsum(rt->ch[0],l,mid,ql,qr);
  if(qr>mid) ans+=qsum(rt->ch[1],mid+1,r,ql,qr);
  return ans;
}
int seg[maxn<<2];
void Insert(int rt,int l,int r,int k){
  seg[rt]++;
  if(l==r)return;
  int mid=(l+r)>>1;
  if(k<=mid)Insert(rt<<1,l,mid,k);
  else Insert(rt<<1|1,mid+1,r,k);
}
int qsum(int rt,int l,int r,int ql,int qr){
  if(ql<=l&&r<=qr){
    return seg[rt];
  }
  int ans=0,mid=(l+r)>>1;
  if(ql<=mid)ans+=qsum(rt<<1,l,mid,ql,qr);
  if(qr>mid) ans+=qsum(rt<<1|1,mid+1,r,ql,qr);
  return ans;
}
int ans[maxn];
struct event{
  int typ,u,v,k,val,num,T;
  bool operator <(const event &B)const{
    return (val==B.val)?typ<B.typ:val<B.val;
  }
}E[maxn*2];
int hit[maxn];
int LCA,sum1=0,sum2=0;
int pathsum(int u,int v,int T){
  int t1=top[u],t2=top[v];
  sum1=sum2=0;
  while(t1!=t2){
    if(depth[t1]<depth[t2]){
      sum2+=qsum(1,1,n,dfn[t2],dfn[v]);sum2+=qsum(Root[T],1,n,dfn[t2],dfn[v]);
      v=prt[t2];t2=top[v];
    }else{
      sum1+=qsum(1,1,n,dfn[t1],dfn[u]);sum1+=qsum(Root[T],1,n,dfn[t1],dfn[u]);
      u=prt[t1];t1=top[u];
    }
  }
  if(depth[u]>depth[v]){
    LCA=v;sum1+=qsum(1,1,n,dfn[v],dfn[u]);sum1+=qsum(Root[T],1,n,dfn[v],dfn[u]);
  }else{
    LCA=u;sum2+=qsum(1,1,n,dfn[u],dfn[v]);sum2+=qsum(Root[T],1,n,dfn[u],dfn[v]);
  }
  return sum1+sum2;
}
int qkth(int rt,node* rt2,int l,int r,int ql,int qr,int k){//from right to left
  if(l==r)return l;
  int mid=(l+r)>>1;
  if(qr<=mid)return qkth(rt<<1,rt2->ch[0],l,mid,ql,qr,k);
  int tmp=qsum(rt<<1|1,mid+1,r,ql,qr)+qsum(rt2->ch[1],mid+1,r,ql,qr);
  if(k<=tmp)return qkth(rt<<1|1,rt2->ch[1],mid+1,r,ql,qr,k);
  else return qkth(rt<<1,rt2->ch[0],l,mid,ql,qr,k-tmp);
}
int kth(int lim,int u,int k,int T){
  int t=top[u];
  while(1){
    int tmp=qsum(1,1,n,dfn[t],dfn[u])+qsum(Root[T],1,n,dfn[t],dfn[u]);
    if(tmp>=k)return qkth(1,Root[T],1,n,dfn[t],dfn[u],k);
    else{
      k-=tmp;u=prt[t];t=top[u];
    }
  }
}
int query(int u,int v,int k,int T){
  int wu=qsum(1,1,n,dfn[u],dfn[u])+qsum(Root[T],1,n,dfn[u],dfn[u]);
  int wv=qsum(1,1,n,dfn[v],dfn[v])+qsum(Root[T],1,n,dfn[v],dfn[v]);
  int ww=pathsum(u,v,T);
  if(ww-wu-wv<k)return -1;
  else{
    if(sum1-wu>=k)return kth(LCA,prt[u],k,T);
    else return kth(LCA,prt[v],(ww-wu-wv-k+1),T);
  }
}
int point[maxn];
int main(){
  freopen("K_night.in","r",stdin);
  freopen("K_night.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",&prt[i]);
  for(int i=1;i<=n;++i){
    if(prt[i])addedge(prt[i],i);
    else root=i;
  }
  depth[root]=1;dfs1(root);top[root]=root;dfs2(root);
  int m;scanf("%d",&m);
  int cntq=0;
  Root[m+1]=t+0;Root[m+1]->ch[0]=Root[m+1]->ch[1]=t+0;
  Root[m+1]->sum=0;
  
  for(int i=1;i<=m;++i){
    scanf("%d",&E[i].typ);
    if(E[i].typ==1){
      scanf("%d",&E[i].u);E[i].val=i;hit[E[i].u]=i;
    }
    else{
      scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].k,&E[i].val);E[i].num=++cntq;E[i].T=i;
    }
  }
  for(int i=m;i>=1;--i){
    Root[i]=Root[i+1];
    if(E[i].typ==1){
      Insert(Root[i],Root[i],1,n,dfn[E[i].u]);
    }
  }
  for(int i=1;i<=n;++i){
    if(!hit[i])Insert(1,1,n,dfn[i]);
  }
  sort(E+1,E+m+1);
  for(int i=1;i<=m;++i){
    if(E[i].typ==1)Insert(1,1,n,dfn[E[i].u]);
    else{
      ans[E[i].num]=query(E[i].u,E[i].v,E[i].k,E[i].T);
    }
  }
  for(int i=1;i<=n;++i)point[dfn[i]]=i;
  for(int i=1;i<=cntq;++i){
    if(ans[i]!=-1)printf("%d\n",point[ans[i]]);
    else printf("-1\n");
  }
  return 0;
}