C++ 解法, 执行用时: 350ms, 内存消耗: 21548K, 提交时间: 2022-05-18 09:44:29

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)

using namespace std;
const int N=600005;
bool vis[N];
int n,m,len,fa[N],id[N],Fa[N],son[N][2],Son[N][2],ans,siz[N];
char s[N];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

void getup(int x)
{
	if(x==1) return;
	int rt=fa[x],lst=x;
	id[x]=x;
	while(!vis[rt]) id[rt]=x,lst=rt,rt=fa[rt];
	Fa[x]=rt;
	if(son[rt][0]==lst) Son[rt][0]=x;
	else Son[rt][1]=x;
}

void getdown(int x)
{
	if(x==1) return;
	int rt=id[x];
	Fa[rt]=x;
	Son[x][(s[1]-'0')^1]=rt;
	vis[x]=1,siz[x]=siz[rt];
}

int dfs(int x,int k)
{
	if(!Son[x][0] && !Son[x][1]) return x;
	if(siz[Son[x][0]]>=k) return dfs(Son[x][0],k);
	return dfs(Son[x][1],k-siz[Son[x][0]]);
}

int main()
{
	n=getint(),m=getint(),getint();
	rep(i,2,n)
	{
		fa[i]=getint();
		son[fa[i]][getint()]=i;
	}
	rep(i,1,n)
	{
		vis[i]=(i==1 || (son[i][0] && son[i][1]) || (!son[i][0] && !son[i][1]));
		if(vis[i] && i>1)
		{
			int lst,x;
			id[i]=i;
			for(lst=i,x=fa[i]; !vis[x]; id[x]=i,lst=x,x=fa[x]);
			Fa[i]=x;
			if(son[x][0]==lst) Son[x][0]=i;
			else Son[x][1]=i;
		}
	}
	id[1]=1;
	repd(i,n,2)
	{
		if(!son[i][0] && !son[i][1]) siz[i]=1;
		if(vis[i]) siz[Fa[i]]+=siz[i];
	}
	while(m--)
	{
		int tp=getint(),x=getint()^ans;
		if(tp==1)
		{
			scanf("%s",s+1),len=strlen(s+1);
			getdown(x),getup(x);
			int lst=n+len;
			for(int y=x,i=1; i<=len; fa[++n]=y,son[y][s[i]-'0']=n,y=n,id[y]=lst,++i);
			vis[n]=1,Fa[n]=x,Son[x][s[1]-'0']=n;
			for(int y=n; y; y=Fa[y]) ++siz[y];
		}
		else
		{
			int k=getint();
			x=id[x];
			int y=x,lst=0;
			while(siz[y]<k) lst=y,y=Fa[y];
			if(y!=x)
			{
				if(Son[y][0]==lst) y=Son[y][1];
				else y=Son[y][0];
				k-=siz[lst];
			}
			printf("%d\n",ans=dfs(y,k));
		}
	}
	return 0;
}