首先吐槽一下bzoj，这CF原题还做成权限题啊？！
需要注意的是，一个点不能被选中当且进当这个点在第y+1年到现在这一段时间内受到攻击，其余的点都可以被选
然后...其实这题的重点在于...码
思想很简单，先树链剖分，然后建起一棵主席树维护，每次修改就生成一个新版本，这样的话用现在的版本-时刻y的版本就可以算出这段时间不能用的点的个数，再用总点数去减就是可以用的个数了
然后在查询时查到一个确定的重链上就可以二分答案了（不建议写倍增，因为倍增的话边界情况不好处理）
其实这种题重点应该是看代码啦...
注意几个细节：
题目要求起点和终点不算，因此我在代码中处理掉了这两个点，把他们上移或下移了一个位置
其次，注意LCA不要被重复统计
而且，一定要注意跳的顺序是起点-LCA-终点，不要像普通的树剖那样起点终点一起跳！
剩下看代码吧
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define ls tree[rt].lson
#define rs tree[rt].rson
using namespace std;
struct Per_Seg_Tree
{
int lson,rson;
int siz;
}tree[8000005];
int rot[100005];
int RT=0;
vector <int> v[100005];
int siz[100005];
int son[100005];
int w[100005];
int f[100005][25];
int nnum[100005];
int ttop[100005];
int onum[100005];
int dep[100005];
int vis[100005];
int tot=0,cnt=0,ts=0;
int n,m;
void dfs(int x,int fx)
{
siz[x]=1,f[x][0]=fx,dep[x]=dep[fx]+1;
int maxh=0;
for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
for(int i=0;i<v[x].size();i++)
{
int to=v[x][i];
if(to==fx)continue;
dfs(to,x);
siz[x]+=siz[to];
if(siz[to]>maxh)maxh=siz[to],son[x]=to;
}
}
void redfs(int x,int fx,int topx)
{
ttop[x]=topx;
nnum[x]=++ts,onum[ts]=x;
if(son[x])redfs(son[x],x,topx);
for(int i=0;i<v[x].size();i++)
{
int to=v[x][i];
if(to==son[x]||to==fx)continue;
redfs(to,x,to);
}
}
void pushup(int rt)
{
tree[rt].siz=tree[ls].siz+tree[rs].siz;
}
void buildtree(int &rt,int l,int r)
{
rt=++tot;
if(l==r){tree[rt].siz=0;return;}
int mid=(l+r)>>1;
buildtree(ls,l,mid),buildtree(rs,mid+1,r);
pushup(rt);
}
void update(int &rt,int lrt,int l,int r,int pos)
{
rt=++tot;
if(l==r){tree[rt].siz=1;return;}
int mid=(l+r)>>1;
if(pos<=mid)rs=tree[lrt].rson,update(ls,tree[lrt].lson,l,mid,pos);
else ls=tree[lrt].lson,update(rs,tree[lrt].rson,mid+1,r,pos);
pushup(rt);
}
int query(int rt1,int rt2,int l,int r,int lq,int rq)
{
if(l>=lq&&r<=rq)return tree[rt2].siz-tree[rt1].siz;
int mid=(l+r)>>1;
int s=0;
if(lq<=mid)s+=query(tree[rt1].lson,tree[rt2].lson,l,mid,lq,rq);
if(rq>mid)s+=query(tree[rt1].rson,tree[rt2].rson,mid+1,r,lq,rq);
return s;
}
int LCA(int x,int y)
{
while(ttop[x]!=ttop[y])
{
if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);
x=f[ttop[x]][0];
}
return dep[x]<dep[y]?x:y;
}
int Jump(int x,int ed)
{
for(int i=20;i>=0;i--)if(dep[f[x][i]]>dep[ed])x=f[x][i];
return x;
}
int upsolve(int fr,int to,int qy,int k)
{
int l=nnum[to],r=nnum[fr],ans=to;
while(l<=r)
{
int mid=(l+r)>>1;
int num=dep[fr]-dep[onum[mid]]+1;
int delt=query(rot[qy],rot[cnt],1,n,mid,nnum[fr]);
if(num-delt>=k)ans=onum[mid],l=mid+1;
else r=mid-1;
}
return ans;
}
int dosolve(int fr,int to,int qy,int k)
{
int l=nnum[to],r=nnum[fr],ans=to;
while(l<=r)
{
int mid=(l+r)>>1;
int num=dep[onum[mid]]-dep[to]+1;
int delt=query(rot[qy],rot[cnt],1,n,nnum[to],mid);
if(num-delt>=k)ans=onum[mid],r=mid-1;
else l=mid+1;
}
return ans;
}
int goup(int st,int ed,int qy,int &k)
{
while(ttop[st]!=ttop[ed])
{
int num=dep[st]-dep[ttop[st]]+1;
int delt=query(rot[qy],rot[cnt],1,n,nnum[ttop[st]],nnum[st]);
if(num-delt>=k)
{
return upsolve(st,ttop[st],qy,k);
}else k-=num-delt,st=f[ttop[st]][0];
}
int num=dep[st]-dep[ed]+1;
int delt=query(rot[qy],rot[cnt],1,n,nnum[ed],nnum[st]);
if(num-delt>=k)
{
return upsolve(st,ed,qy,k);
}else {k-=num-delt;return 0;}
}
int godown(int st,int ed,int qy,int k)
{
if(st==ed)
{
if(k==1&&vis[st]<=qy)return st;
else return 0;
}
stack <int> S;
while(ttop[st]!=ttop[ed])S.push(st),S.push(ttop[st]),st=f[ttop[st]][0];
if(st!=ed)S.push(st);
else
{
if(vis[ed]<=qy)
{
if(k==1)return ed;
else k--;
}
ed=S.top();S.pop();
}
while(!S.empty())
{
int u=S.top();
S.pop();
int num=dep[u]-dep[ed]+1;
int delt=query(rot[qy],rot[cnt],1,n,nnum[ed],nnum[u]);
if(num-delt>=k)
{
return dosolve(u,ed,qy,k);
}else
{
k-=num-delt;
if(!S.empty()){ed=S.top();S.pop();}
}
}
return 0;
}
/*inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}*/
int main()
{
//n=read();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i][0]);
if(f[i][0])v[f[i][0]].push_back(i);
else RT=i;
}
dfs(RT,RT);
redfs(RT,RT,RT);
buildtree(rot[0],1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int typ;
scanf("%d",&typ);
if(typ==1)
{
int p;
w[i]=++cnt;
scanf("%d",&p);
update(rot[cnt],rot[cnt-1],1,n,nnum[p]),vis[p]=cnt;
}else
{
w[i]=w[i-1];
int st,ed,k,y;
scanf("%d%d%d%d",&st,&ed,&k,&y);
if(f[st][0]==ed||f[ed][0]==st){printf("-1\n");continue;}
y=w[y];
int fa=LCA(st,ed);
if(fa==st)
{
st=Jump(ed,fa),ed=f[ed][0];
int t=godown(ed,st,y,k);
if(!t)printf("-1\n");
else printf("%d\n",t);
}else if(fa==ed)
{
ed=Jump(st,fa),st=f[st][0];
int t=goup(st,ed,y,k);
if(!t)printf("-1\n");
else printf("%d\n",t);
}else
{
st=f[st][0],ed=f[ed][0];
int t=goup(st,fa,y,k);
if(t)printf("%d\n",t);
else if(ed==fa){printf("-1\n");continue;}
else
{
fa=Jump(ed,fa);
t=godown(ed,fa,y,k);
if(t)printf("%d\n",t);
else printf("-1\n");
}
}
}
}
return 0;
}