Problem F:Marked Ancestor
You are given a treeTthat consists ofNnodes. Each node is numbered from 1 toN, and node 1 is always the root node ofT. Consider the following two operations onT:
M v: (Mark) Mark nodev.Q v: (Query) Print the index of the nearest marked ancestor of nodevwhich 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 integersNandQ, which denotes the number of nodes in the treeTand the number of operations, respectively. These numbers meet the following conditions: 1 ≤N≤ 100000 and 1 ≤Q≤ 100000.
The followingN- 1 lines describe the configuration of the treeT. Each line contains a single integerpi(i= 2, … ,N), which represents the index of the parent ofi-th node.
The nextQlines contain operations in order. Each operation is formatted as "M v" or "Q v", wherevis 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 Input6 311233Q 5M 3Q 50 0Output for the Sample Input4
题意：给出包含n个节点的树，初始时节点1的父节点为1并被标记，再给出其他n-1个节点的父节点，Q次询问，M x表示把节点x标记；Q x表示找出离x最近的被标记的父节点的编号，，最后输出所有标号之和。
思路：基础的并查集了，只不过这里要注意的是：寻找父节点时不要压缩路径。还要使用long long 。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;ll father[maxn];int n,q;ll find_father(ll x){if (x==father[x])return father[x];return find_father(father[x]);}int main(){int i,j;ll x;char s[2];while (sff(n,q)){if (n==0&&q==0) break;father[1]=1;FRE(i,2,n){sf(x);father[i]=x;}ll ans=0;while (q–){scanf("%s%lld",s,&x);if (s[0]=='M')father[x]=x;elseans+=find_father(x);}pf("%lld\n",ans);}return 0;}
肯承认错误则错已改了一半
