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可能溢出。

 #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 ;

 }

巴特西

AOJ 2170 Marked Ancestor （基础并查集）

最新文章

热门文章