AOJ 2170 Marked Ancestor （基础并查集）

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=45522

给定一棵树的n个节点，每个节点标号在1到n之间，1是树的根节点，有如下两种操作：

M v ：把编号为v的节点标记。

Q v ：查询与v节点距离最近的被标记的点的编号。最初只有根节点被标记。

输入n-1个数表示，每一个数是当前第i个数的父节点，输出对于每个查询得到标号的总和。

并查集与树的结合，在输入的时候就可以根据父节点的关系建立并查集，1的父亲是1.

还有把编号为v的节点标记的意思是等同于把这颗子树从并查集里面分出来。因为只要这个节点被标记，那么他的字节点一定是到这个节点的距离最小。

理解清楚这题就很简单，只涉及到查找这个操作。注意sum可能溢出。

 1 #include<cstdio>
 2 int par[100010];
 3 int find(int x)
 4 {
 5     if(x==par[x]) return x;
 6     return find(par[x]);
 7 }
 8 int main()
 9 {
10     int n,q,a,b;
11     while(~scanf("%d%d",&n,&q))
12     {
13         if(n==0&&q==0) break;
14         for(int i=2;i<=n;i++)
15         {
16             scanf("%d",&par[i]);
17         }
18         par[1]=1;
19         long long sum=0;
20         char s[5];
21         while(q--)
22         {
23             scanf("%s%d",s,&b);
24             if(s[0]=='Q') sum+=find(b);
25             else if(s[0]=='M') par[b]=b;  //分离 b节点
26         }
27         printf("%lld
",sum);
28     }
29     return 0;
30 }