题目链接：https://www.nowcoder.com/acm/contest/94/B
题意：在一棵有 n 个节点的树上，有两种操作，一个是把 u 到 v 的路径走一遍，另一个是查询 u 到 fa[ u ]的路径走了几次，如果没走过输出“ Not yet ”，走过一次升序输出经过要走这条路时的路径端点，否则输出“ Many Times”。
题解：因为只需记录每条路径经过一次，若一条路径经过了多次，则访问该节点时可跳到它的没有访问过路径的祖先上面，故可以使用并查集来实现。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define mst(a,b) memset((a),(b),sizeof(a)) 5 #define pi acos(-1) 6 #define pii pair<int,int> 7 const int INF = 0x3f3f3f3f; 8 const double eps = 1e-3; 9 const int MAXN = 1e5 + 10; 10 const int MAXM = 2e6 + 10; 11 const ll mod = 1e9 + 7; 12 13 int n; 14 int num[MAXN],fa[MAXN],pre[MAXN],dep[MAXN]; 15 int ansl[MAXN],ansr[MAXN]; 16 17 int findd(int x) { 18 if(pre[x] == x) return x; 19 return pre[x] = findd(pre[x]); 20 } 21 22 void update(int u,int v) { 23 int a = u, b = v; 24 while(u != v) { 25 if(dep[u] < dep[v]) swap(u,v); 26 num[u]++; 27 if(num[u] == 1) 28 ansl[u] = min(a,b),ansr[u] = max(a,b); 29 else 30 pre[u] = fa[u]; 31 u = findd(fa[u]); 32 } 33 } 34 35 int main() 36 { 37 #ifdef local 38 freopen("data.txt","r",stdin); 39 // freopen("data.txt","w",stdout); 40 #endif 41 while(~scanf("%d",&n)) { 42 mst(num,0); 43 for(int i=1; i<n; i++) { 44 int x; 45 scanf("%d",&x); 46 fa[i] = x; 47 pre[i] = i; 48 dep[i] = dep[x] + 1; 49 } 50 int q; 51 scanf("%d",&q); 52 while(q--) { 53 char s[5]; 54 scanf("%s",s); 55 if(s[0] == 'R') { 56 int u,v; 57 scanf("%d%d",&u,&v); 58 update(u,v); 59 } 60 else { 61 int u; 62 scanf("%d",&u); 63 if(num[u] == 0) puts("Not yet"); 64 else if(num[u] == 1) printf("%d %d ",ansl[u],ansr[u]); 65 else puts("Many times"); 66 } 67 } 68 } 69 return 0; 70 }