Aizu2170 Marked Ancestor（并查集）

并查集用于管理元素分组情况。

建树pre[]记录父节点，一开始只有结点1被标记了，所以find()最终得到的根都是1.

如果遇到M操作，即将树断开（很神奇的操作）。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<stack>
 8 #define lson l, m, rt<<1
 9 #define rson m+1, r, rt<<1|1
10 #define IO ios::sync_with_stdio(false);cin.tie(0);
11 #define INF 0x3f3f3f3f
12 typedef unsigned long long ll;
13 using namespace std;
14 int n, q, m, pre[100010];
15 char c;
16 int find(int x)
17 {
18     while(x != pre[x]){
19         x = pre[x];
20     }
21     return x;
22 }
23 int main()
24 {
25     IO;
26     while(cin >> n >> q){ 
27         if(!n&&!q) break;
28         ll sum=0;
29         pre[1] = 1;
30         for(int i = 2; i <= n; i++){
31             cin >> pre[i];
32         }
33         for(int i = 0; i < q; i++){
34             cin >> c >> m;
35             if(c == 'Q') 
36                 sum += find(m);
37             else {
38                 pre[m] = m;//断开 
39             }
40         }
41         cout << sum << endl;
42     }
43     return 0;
44 }