Aizu 2170 Marked Ancestor

Marked Ancestor

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem F: Marked Ancestor

You are given a tree T that consists of N nodes. Each node is numbered from 1 to N, and node 1 is always the root node of T. Consider the following two operations on T:

M v: (Mark) Mark node v.
Q v: (Query) Print the index of the nearest marked ancestor of node v which is nearest to it. Initially, only the root node is marked.

Your job is to write a program that performs a sequence of these operations on a given tree and calculates the value that each Q operation will print. To avoid too large output file, your program is requested to print the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to calculate every output of query operations in a given sequence.

Input

The input consists of multiple datasets. Each dataset has the following format:

The first line of the input contains two integers N and Q, which denotes the number of nodes in the tree T and the number of operations, respectively. These numbers meet the following conditions: 1 ≤ N ≤ 100000 and 1 ≤Q ≤ 100000.

The following N - 1 lines describe the configuration of the tree T. Each line contains a single integer p_i (i = 2, ... , N), which represents the index of the parent of i-th node.

The next Q lines contain operations in order. Each operation is formatted as "M v" or "Q v", where v is the index of a node.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the sum of the outputs of all query operations in one line.

Sample Input

Output for the Sample Input

一道比较简单的并查集问题，先给定一棵树，对于这棵树有两个操作，M i表示将i的所有子孙节点以i为树根从原树中分离出来，Q i表示询问节点i的树根是多少

用数组tree[i]记录节点i的父亲节点，若i是根节点就记为i

这样对于两种操作我们只要如下处理即可：

M i：将tree[i]改为它本身，也就是i

Q i：从i向上查找直到找到它的根节点

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int n,q;
 7 int tree[100050];
 8 
 9 int Find(int x)
10 {
11     if(tree[x]==x)
12         return x;
13     return Find(tree[x]);
14 }
15 
16 int main()
17 {
18     while(scanf("%d %d",&n,&q)==2)
19     {
20         if(n==0&&q==0)
21             break;
22         tree[1]=1;
23         for(int i=2;i<=n;i++)
24             scanf("%d",&tree[i]);
25         getchar();
26         long long ans=0;
27         for(int i=1;i<=q;i++)
28         {
29             int temp;
30             char s[100];
31             gets(s);
32             sscanf(&s[2],"%d",&temp);
33             if(s[0]=='M')
34                 tree[temp]=temp;
35             else if(s[0]=='Q')
36                 ans+=Find(temp);
37         }
38         cout<<ans<<endl;
39     }
40 
41     return 0;
42 }

[C++]