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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;
const int N=1e5;
int rt[N<<2],in[N],out[N],n,m,cnt,T;
vector<int> g[N],em[N];
char c;
void (){rep(i,1,n){g[i].clear();em[i].clear();}}
inline void dfs(int x){
in[x]=++cnt;
for(int i=0;i<g[x].size();++i)dfs(g[x][i]);
out[x]=cnt;
}
inline void pushdown(int o){rt[o<<1]=rt[o<<1|1]=rt[o];rt[o]=-1;}
inline void build(int o,int l,int r){
rt[o]=-1;
if(l==r)return ;
int mid=l+r>>1;
build(lson);
build(rson);
}
inline void update(int o,int l,int r,int L,int R,int x){
if(L==l&&R==r){rt[o]=x;return;}
if(rt[o]!=-1)pushdown(o);
int mid=l+r>>1;
if(R<=mid)update(lson,L,R,x);
else if(L>mid)update(rson,L,R,x);
else {
update(lson,L,mid,x);
update(rson,mid+1,R,x);
}
}
inline int query(int o,int l,int r,int x){
if(l==r)return rt[o];
if(rt[o]!=-1)pushdown(o);
int mid=l+r>>1;
if(x<=mid)return query(lson,x);
else return query(rson,x);
}
int main(){
ios::sync_with_stdio(false);
cin>>T;
rep(cs,1,T){
cnt=0;
cin>>n;
build(1,1,n);
init();
rep(i,1,n-1){
int x,y;
cin>>x>>y;
g[y].push_back(x);
em[x].push_back(y);
}
rep(i,1,n)if(em[i].size()==0)dfs(i);
cin>>m;
cout<<"Case #"<<cs<<":"<<endl;
while(m--){
char c;cin>>c;
if(c=='C'){
int x;cin>>x;
cout<<query(1,1,n,in[x])<<endl;
}
else {int x,y;cin>>x>>y;
update(1,1,n,in[x],out[x],y);
}
}
}
return 0;
}
|
近期评论