一级棒！

输入包含多组数据，请处理到文件结束。
每组数据，第一行是一个正整数 N (2<= N <= 100,000)表示树的节点个数；
第二行包括N-1个数，其中第i个数{pi}，表示节点 i 的父节点编号为pi(pi < i)（节点编号从0开始）；
第三行是一个正整数Q(1<=Q<=200,000)；
接下来的Q行有两种形式的命令
1. R u v ，表示ACSquare想起已经经过了u，v（编号从0开始）间的路径一次，
2. W v，表示ACSquare想让你根据他想起的信息，回答(v,pv),(v与pv间的边,其中v != 0)，即根据目前给出的 1 形式的信息，回答边被经过的相关信息。

对于每个第二中形式的命令，做出回答。
1.若(v,pv),还未被经过，则回答"Not yet"；
2.若(v,pv),恰好是“一级棒的边”，回答恰好经过这条边的路径端点，按升序在一行内输出；
3.若(v,pv),被超过一次经过，则回答"Many times"。
注意，若多次想起同一对点对，应该当做不同的路径对来处理。

C++14(g++5.4) 解法, 执行用时: 550ms, 内存消耗: 17384K, 提交时间: 2020-04-19 16:58:09

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=(int)1e5+10;
int par[maxn],dep[maxn],num[maxn],s[maxn],t[maxn],far[maxn];
char op[2];
inline int Find(int x)
{
	return par[x]==x?x:par[x]=Find(par[x]);
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<n;++i)
		{
			scanf("%d",&far[i]);
			num[i]=0;
			par[i]=i;
			dep[i]=dep[far[i]]+1;
		}
		int q,u,v,x,y;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%s",op);
			if(op[0]=='R')
			{
				scanf("%d%d",&u,&v);
				x=u;
				y=v;
				while(x!=y)
				{
					if(dep[x]<dep[y])
					{
						swap(x,y);
					}
					if((++num[x])<=1)
					{
						s[x]=min(u,v);
						t[x]=max(u,v);
					}
					else
					{
						par[x]=far[x];
					}
					x=Find(far[x]);
				}
			}
			else
			{
				scanf("%d",&u);
				if(num[u]==0)
				{
					puts("Not yet");
				}
				else if(num[u]==1)
				{
					printf("%d %d\n",s[u],t[u]);
				}
				else
				{
					puts("Many times");
				}
			}
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 695ms, 内存消耗: 7700K, 提交时间: 2019-11-01 08:04:50

#include<iostream>
#include<stdio.h>
using namespace std;
const int N=1e5+10;
int fa[N],f[N],cnt[N],dep[N],l[N],r[N];
int find(int x) {
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
int main() {
	char s[2];
	int n,i,q,x,y;
	while(~scanf("%d",&n)) {
		for(i=1; i<n; ++i) {
			scanf("%d",&fa[i]);
			dep[i]=dep[fa[i]]+1;
			f[i]=i,cnt[i]=0;
		}
		scanf("%d",&q);
		while(q--) {
			scanf("%s",s);
			if(s[0]=='R') {
				scanf("%d%d",&x,&y);
				if(x>y)swap(x,y);
				int u=x,v=y;
				while(u!=v) {
					if(dep[u]<dep[v])swap(u,v);
					cnt[u]++;
					if(cnt[u]==1)l[u]=x,r[u]=y;
					else f[u]=fa[u];
					u=find(fa[u]);
				}
			} else {
				scanf("%d",&x);
				if(!cnt[x])printf("Not yet\n");
				else if(cnt[x]==1)printf("%d %d\n",l[x],r[x]);
				else if(cnt[x]>1)printf("Many times\n");
			}
		}
	}
}

详情