Cutting Tree

题目连接：

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

Hint

题意

给你个森林，俩操作，1是砍掉与他父亲的连边，2是查询xy是否在同一个连通块里面

题解：

倒着做，砍边就变成连边了，然后并茶几莽一波就好了

代码

#include
    
     using namespace std;const int maxn = 2e4+7;int cas = 0;int fa[maxn];int e[maxn];int flag[maxn];int a[maxn],b[maxn],c[maxn];;int fi(int x){    if(x==fa[x])return x;    return fa[x]=fi(fa[x]);}void init(){    memset(flag,0,sizeof(flag));}void solve(){    init();    vector
     
      ans;    int n,m;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        fa[i]=i;    for(int i=1;i<=n;i++)        scanf("%d",&e[i]);    for(int i=1;i<=m;i++){        string s;cin>>s;        if(s[0]=='C'){            a[i]=1;            scanf("%d",&b[i]);            flag[b[i]]++;        }else{            a[i]=0;            scanf("%d%d",&b[i],&c[i]);        }    }    for(int i=1;i<=n;i++){        if(flag[i]==0&&e[i]!=0){            fa[fi(i)]=fi(e[i]);        }    }    for(int i=m;i>=1;i--){        if(a[i]==1){            flag[b[i]]--;            if(flag[b[i]]==0&&e[b[i]]!=0)                fa[fi(b[i])]=fi(e[b[i]]);        }else{            if(fi(b[i])==fi(c[i]))ans.push_back(1);            else ans.push_back(0);        }    }    for(int i=ans.size()-1;i>=0;i--){        if(ans[i])printf("YES\n");        else printf("NO\n");    }}int main(){    //freopen("1.txt","r",stdin);    int t;    scanf("%d",&t);    while(t--){        printf("Case #%d:\n",++cas);        solve();    }    return 0;}