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可能溢出。
#include<cstdio>
int par[];
int find(int x)
{
if(x==par[x]) return x;
return find(par[x]);
}
int main()
{
int n,q,a,b;
while(~scanf("%d%d",&n,&q))
{
if(n==&&q==) break;
for(int i=;i<=n;i++)
{
scanf("%d",&par[i]);
}
par[]=;
long long sum=;
char s[];
while(q--)
{
scanf("%s%d",s,&b);
if(s[]=='Q') sum+=find(b);
else if(s[]=='M') par[b]=b; //分离 b节点
}
printf("%lld\n",sum);
}
return ;
}