一堆乱七八糟的东西套来套去，特判又多，写起来都蛋疼。

还好写完了。

首先，主席树维护蛮子进攻；然后LCA处理一下暴力搞，复杂度似乎科学？

# include <stdio.h>

using namespace std;

const int M=200010;
int ch[M*20][2],s[M*20],root[M],tot=0,n,roots;

int fa[M][23],head[M],next[M],to[M],tott=0;

int dfn1[M],dfn2[M],dfnt,dep[M];

inline void add(int u,int v) {
	++tott;
	next[tott]=head[u];
	head[u]=tott;
	to[tott]=v;
}

inline void dfs(int x,int d) {
	dfn1[x]=++dfnt;
	dep[x]=d;
	for (int i=1;i<=17;++i)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int i=head[x];i;i=next[i]) dfs(to[i],d+1);
	dfn2[x]=dfnt;
}

inline int lca(int u,int v) {
	if (dep[u]<dep[v]) {
		int t=u;
		u=v;
		v=t;
	}
	for (int i=20;i>=0;--i)
		if((dep[u]-dep[v])&(1<<i)) u=fa[u][i];
	if(u==v) return u;
	for (int i=20;i>=0;--i) {
		if(fa[u][i]!=fa[v][i]) {
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}



inline void ins(int root1,int &root,int l,int r,int L,int R) {
	root=++tot;
	ch[root][0]=ch[root1][0];
	ch[root][1]=ch[root1][1];
	s[root]=s[root1];
	if(L<=l && r<=R) {
		s[root]++;
		return ;
	}
	int mid=l+r>>1;
	if(L<=mid) ins(ch[root1][0],ch[root][0],l,mid,L,R);
	if(R>mid) ins(ch[root1][1],ch[root][1],mid+1,r,L,R);
}

inline int query(int root1,int root2,int l,int r,int x) {
	if(x<l || x>r) return 0;
	if(l==r) return s[root1]-s[root2];
	int mid=l+r>>1,res=0;
	if(x<=mid) res=query(ch[root1][0],ch[root2][0],l,mid,x);
	else res=query(ch[root1][1],ch[root2][1],mid+1,r,x);
	return res+s[root1]-s[root2];
}

inline int LCA_go(int from,int left,int rootsn,int y,int from_attack) {
	for (int i=20;i>=0;--i) {
		int go=fa[from][i];
		if(go!=0) {
			int go_attack=dep[go]-query(root[rootsn],root[y],1,n,dfn1[go]);
			if(from_attack-go_attack<left) from=go;
		}
	}
	return from;
}
int main() {
//	freopen("path.in","r",stdin);
//	freopen("path.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i) {
		int father; scanf("%d",&father);
		if(father==0) roots=i;
		else {
			fa[i][0]=father;
			add(father,i);
		}
	}
	dfs(roots,1);
	int Q,buff;
	scanf("%d",&Q);
	for (int rootsn=1; rootsn<=Q; ++rootsn) {
		scanf("%d",&buff);
		if(buff==1) {
			int x;
			scanf("%d",&x);
			ins(root[rootsn-1],root[rootsn],1,n,dfn1[x],dfn2[x]);
		} else {
			int a,b,k,y;
			root[rootsn]=root[rootsn-1];
			scanf("%d%d%d%d",&a,&b,&k,&y);
			int LCA=lca(a,b),lca_attack,lcafa_attack,a_attack,b_attack,afa_attack,bfa_attack;
			a_attack=dep[a]-query(root[rootsn],root[y],1,n,dfn1[a]);
			b_attack=dep[b]-query(root[rootsn],root[y],1,n,dfn1[b]);
			lca_attack=dep[LCA]-query(root[rootsn],root[y],1,n,dfn1[LCA]);
			lcafa_attack=dep[fa[LCA][0]]-query(root[rootsn],root[y],1,n,dfn1[fa[LCA][0]]);
			afa_attack=dep[fa[a][0]]-query(root[rootsn],root[y],1,n,dfn1[fa[a][0]]);
			bfa_attack=dep[fa[b][0]]-query(root[rootsn],root[y],1,n,dfn1[fa[b][0]]);
			int canstop=afa_attack+bfa_attack-lca_attack-lcafa_attack;
			if(canstop<k) {
				printf("-1\n");
			} else {
				int LCA_left=afa_attack-lcafa_attack;
				if(b==LCA) LCA_left-=b_attack-bfa_attack;
				if(k<=LCA_left) {
					// k is in left
					printf("%d\n",LCA_go(a,k+a_attack-afa_attack,rootsn,y,a_attack));
				} else {
					// k is in right
					printf("%d\n",LCA_go(b,canstop-k+1+b_attack-bfa_attack,rootsn,y,b_attack));
				}
			}
		}
	}
	return 0;
}