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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include<vector>
using namespace std;
const int siz = 1e5 + 5;
int id = 1;
vector<int> G[siz];
int ll[siz],rr[siz],vis[siz];
struct tree
{
int l, r;
int date;
} tree[siz << 2];
void pushDown(int i)
{
if(tree[i].date==-1) return ;
tree[i << 1].date = tree[i].date;
tree[i << 1 | 1].date=tree[i].date;
tree[i].date = -1;
}
void build_tree(int i,int l,int r)
{
tree[i].l = l;
tree[i].r = r;
tree[i].date = -1;
int mid = l + r >> 1;
if(l==r)
return;
build_tree(i << 1, l, mid);
build_tree(i << 1 | 1, mid + 1, r);
}
void Change(int i,int L,int R,int p){
if(L<=tree[i].l&&tree[i].r<=R){
tree[i].date=p;
return;
}
pushDown(i);
int m=(tree[i].l+tree[i].r)>>1;
if(L<=m)
Change(i<<1,L,R,p);
if(R>m)
Change(i<<1|1,L,R,p);
}
int query(int i,int index){
if(tree[i].l==tree[i].r)
return tree[i].date;
pushDown(i);
int m=(tree[i].l+tree[i].r)>>1;
if(index<=m)
query(i<<1,index);
else
query(i<<1|1,index);
}
void dfs(int s){
int i,tmp;
ll[s]=id++;
for(i=0;i<G[s].size();i++){
tmp=G[s][i];
dfs(tmp);
}
rr[s]=id++;
}
int main()
{
char ch;
int t,n,m,u,v,i,cas=1;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
build_tree(1,1,2*n);
for(i=1;i<=n;i++)
vis[i]=0,G[i].clear();
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
G[v].push_back(u);
vis[u]=1;
}
memset(ll,-1,sizeof(ll));
memset(rr,-1,sizeof(rr));
id=1;
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i);
scanf("%d",&m);
printf("Case #%d:n",cas++);
while(m--){
cin>>ch;
if(ch=='C'){
scanf("%d",&u);
printf("%dn",query(1,ll[u]));
}
else{
scanf("%d%d",&u,&v);
Change(1,ll[u],rr[u],v);
}
}
}
}
|
近期评论