题目链接：https://vjudge.net/problem/UVALive-6910

Description

Tree in graph theory refers to any connected graph (of nodes and edges) which has no simple cycle,
while forest corresponds to a collection of one or more trees. In this problem, you are given a forest of
N nodes (of rooted trees) and K queries. Each query is in the form of:
• C x : remove the edge connecting node and its parent. If node has no parent, then ignore this
query.
• Q a b : output ‘YES’ if there is a path from node to node in the forest; otherwise, ‘NO’.
For example, let the initial forest is shown by Figure 1.
Figure 1. Figure 2.
Let’s consider the following queries (in order):
1) Q 5 7 : output YES.
2) C 2 : remove edge (2, 1) — the resulting forest is shown in Figure 2.
3) Q 5 7 : output NO, as there is no path from node 5 to node 7 in Figure 2.
4) Q 4 6 : output YES.
Input

The first line of input contains an integer T (T ≤ 50) denoting the number of cases. Each case begins
with two integers: N and K (1 ≤ N ≤ 20, 000; 1 ≤ K ≤ 5, 000) denoting the number of nodes in the
forest and the number of queries respectively. The nodes are numbered from 1 to N. The next line
contains N integers Pi (0 ≤ Pi ≤ N) denoting the parent of i-th node respectively. Pi = 0 means that
node i does not have any parent (i.e. it’s a root of a tree). You are guaranteed that the given input
corresponds to a valid forest. The next K lines represent the queries. Each query is in the form of ‘C
x’ or ‘Q a b’ (1 ≤ x, a, b ≤ N), as described in the problem statement above
Output

For each case, output ‘Case #X:’ in a line, where X is the case number starts from 1. For each ‘Q
a b’ query in the input, output either ‘YES’ or ‘NO’ (without quotes) in a line whether there is a path
from node a to node b in the forest.
Explanation for 2nd sample case:
The initial forest is shown in Figure 3 below.
1) C 3 : remove edge (3, 2) — the resulting forest is shown in Figure 4.
2) Q 1 2 : output YES.
3) C 1 : remove edge (1, 2) — the resulting forest is shown in Figure 5.
4) Q 1 2 : output NO as there is no path from node 1 to node 2 in Figure 5
Sample Input

4
7 4
0 1 1 2 2 2 3
Q 5 7
C 2
Q 5 7
Q 4 6
4 4
2 0 2 3
C 3
Q 1 2
C 1
Q 1 2
3 5
0 3 0
C 1
Q 1 2
C 3
C 1
Q 2 3
1 1
0
Q 1 1
Sample Output

Case #1:
YES
NO
YES
Case #2:
YES
NO
Case #3:
NO
YES
Case #4:
YES

题意：给你个森林，俩操作，1是砍掉与他父亲的连边，2是查询xy是否在同一个连通块里面
解法：倒着做，砍边就变成连边了，然后dsu莽一波就好了

//LA 6910
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int n, q, ans[maxn], a[maxn], b[maxn], fa[maxn], cnt[maxn];
namespace dsu{
    int par[maxn];
    inline void init(){for(int i = 1; i <= n; i++) par[i] = i;}
    inline int find_set(int x){if(x == par[x]) return x; return par[x] = find_set(par[x]);}
    inline void union_set(int x, int y){x = find_set(x), y = find_set(y); if(x != y) par[x] = y;}
}
using namespace dsu;

int main()
{
    int T, ks = 0; scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) scanf("%d", &fa[i]);
        init();
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= q; i++){
            char cmd[5]; b[i] = 0;
            scanf("%s%d", cmd, &a[i]);
            if(cmd[0] == 'Q') scanf("%d", &b[i]);
            else ++cnt[a[i]];
        }
        for(int i = 1; i <= n; i++){
            if(!fa[i] || cnt[i]) continue;
            union_set(i, fa[i]);
        }
        for(int i = q; i >= 1; i--){
            if(b[i]) ans[i] = find_set(a[i]) == find_set(b[i]);
            else if(--cnt[a[i]] == 0 && fa[a[i]]){
                union_set(a[i], fa[a[i]]);
            }
        }
        printf("Case #%d:\n", ++ks);
        for(int i = 1; i <= q; i++){
            if(b[i]){
                puts(ans[i] ? "YES" : "NO");
            }
        }
    }
    return 0;
}