一级棒！

树链剖分 改了好几次，发现-1比0跑的快，同时加读入优化可以节省约1000ms。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=100100;

struct edge{
   int to,nxt;
}e[MAXN<<2];

int tot=0;
int head[MAXN];

void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}

int siz[MAXN];
int dep[MAXN];
int fa[MAXN];
int son[MAXN];

void dfs1(int x,int fath,int deep){
   dep[x]=deep;
   siz[x]=1;
   fa[x]=fath;
   int maxson=-1;
   //printf("x=%d\n",x);
   for (int i=head[x];i!=-1;i=e[i].nxt){
   	int v=e[i].to;
   	if (v==fa[x]) continue;
   	dfs1(v,x,deep+1);
   	siz[x]+=siz[v];
   	if (siz[v]>maxson){
   		maxson=siz[v];
         son[x]=v;	    
	 }
   }	
}

int top[MAXN];
int pos[MAXN];
int SEG;

void dfs2(int u,int sp){
	top[u]=sp;
	if (son[u]!=-1)
	  {
	  	pos[u]=SEG++;
	  	dfs2(son[u],sp);
	  }
	else {
	  pos[u]=SEG++;
	  return;
	}
	
	for (int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if (v!=son[u]&&v!=fa[u])
		  dfs2(v,v); 
	}
}


int sum[MAXN<<2];
int col1[MAXN<<2];
int col2[MAXN<<2];
int lazysum[MAXN<<2];
int n; 

void pushdown(int rt,int ln,int rn){
	if (lazysum[rt]){
		lazysum[rt<<1]+=lazysum[rt];
		lazysum[rt<<1|1]+=lazysum[rt];
		sum[rt<<1]+=lazysum[rt];
		sum[rt<<1|1]+=lazysum[rt];
		lazysum[rt]=0;
	}
	if (col1[rt]!=-1){
		col1[rt<<1]=col1[rt];
		col1[rt<<1|1]=col1[rt];
		col1[rt]=-1;
	}
	if (col2[rt]!=-1){
		col2[rt<<1]=col2[rt];
		col2[rt<<1|1]=col2[rt];
		col2[rt]=-1;
	}
}

void update(int L,int R,int A,int B,int l,int r,int rt){
	if (L<=l&&r<=R)
	{
	    col1[rt]=A;
		col2[rt]=B;
		lazysum[rt]+=1;
		sum[rt]+=1;
		return; 
	}
	int m=(l+r)>>1;
	if (L<=m)
	 update(L,R,A,B,l,m,rt<<1);
	if (R>m)
	 update(L,R,A,B,m+1,r,rt<<1|1);
}

int query(int L,int l,int r,int rt){
	if (l==r) return rt;
	int m=(l+r)>>1;
	pushdown(rt,m-l+1,r-m);
	if (L<=m) return query(L,l,m,rt<<1);
    else return query(L,m+1,r,rt<<1|1);
}

void update(int u,int v,int A,int B){
	int f1=top[u],f2=top[v];
	while (f1!=f2){
		if (dep[f1]<dep[f2]){
			swap(f1,f2);
			swap(u,v);
		}
		update(pos[f1],pos[u],A,B,1,n,1);
		u=fa[f1];
		f1=top[u];
	}
	if (u==v) return;
    if (dep[u]>dep[v]) swap(u,v);
    update(pos[son[u]],pos[v],A,B,1,n,1);
}

void init(){
	tot=0;
	memset(head,-1,sizeof(head));
	SEG=1;
	memset(son,-1,sizeof(son));
	memset(sum,0,sizeof(sum));
	memset(lazysum,0,sizeof(lazysum));
	memset(col1,-1,sizeof(col1));
	memset(col2,-1,sizeof(col2)); 
}
int main(){
	

	while (~scanf("%d",&n)){
		init();
		int u;
		for (int i=1;i<=n-1;i++)
	   {
	   	scanf("%d",&u);
	   	addedge(i+1,u+1);
	   	addedge(u+1,i+1);
	   }
	   dfs1(1,0,1);
	   dfs2(1,1); 
	   
	   int q;
	   scanf("%d",&q);
	   
	   char op[5];
	   while (q--){
	   	int u,v;
	   	scanf("%s",op);
	   	if (op[0]=='R'){
	   		scanf("%d%d",&u,&v);
	   		u++;v++;
	   		update(u,v,u,v);
		   }
		else {
			scanf("%d",&u);
			u++;
			int id=query(pos[u],1,n,1);
			int num=sum[id];
			if (num==0)
			 printf("Not yet\n");
			if (num>1)
			 printf("Many times\n");
			if (num==1)
			{
				u=col1[id];
				v=col2[id];
				printf("%d %d\n",min(u,v)-1,max(u,v)-1);
			}
		}
	   }
	   
	}
   return 0;
}