/
3120.test.cpp
58 lines (50 loc) · 1.13 KB
/
3120.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3120
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../linkcuttree/base.cpp"
#include "../../linkcuttree/subtree.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
using Node = NodeBase<int>;
constexpr size_t LIM = 1e5+100;
using LCT = Subtree<Node, LIM>;
LCT lct;
int n,q;
cin>>n>>q;
for(int i=0;i<=n;i++) lct.create(1);
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
lct.evert(lct[b]);
lct.link(lct[a],lct[b]);
}
lct.evert(lct[1]);
lct.link(lct[0],lct[1]);
vector<int> par(n+1);
for(int i=1;i<=n;i++) par[i]=lct.idx(lct.parent(lct[i]));
for(int i=0;i<q;i++){
int t,v;
cin>>t>>v;
if(t==1){
if(lct.root(lct[v])==lct[v]){
lct.link(lct[par[v]],lct[v]);
}else{
lct.cut(lct[v]);
}
}
if(t==2){
auto r=lct.root(lct[v]);
lct.evert(lct[v]);
auto u=lct.parent(r);
lct.evert(r);
lct.cut(u);
cout<<lct.query(u)<<"\n";
lct.link(r,u);
}
}
cout<<flush;
return 0;
}