#include <bits/stdc++.h> #include <iostream> using namespace std; #define ll long long const int maxn = 100005; struct Node{ int l,r; ll pre,add; }node[maxn*4]; void build(int p,int l,int r){ node[p].l = l; node[p].r = r; node[p].pre = -1; node[p].add = -1; if(l==r) return ; int mid = (l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); } void spread(int p){ if(node[p].add!=-1){ node[p*2].pre = node[p].add; node[p*2+1].pre = node[p].add; node[p*2].add = node[p].add; node[p*2+1].add = node[p].add; node[p].add = -1; } } void change(int p,int l,int r,int v) { if(l<=node[p].l&&node[p].r<=r){ node[p].pre = v; node[p].add = v; return ; } spread(p); int mid = (node[p].l+node[p].r)>>1; if(l<=mid)change(p*2,l,r,v); if(r>mid)change(p*2+1,l,r,v); } void query(int p,int l,int r){ if(l<=node[p].l&&node[p].r<=r){ printf("%d\n",node[p].pre); return ; } spread(p); int mid = (node[p].l+node[p].r)>>1; if(l<=mid)query(p*2,l,r); if(r>mid)query(p*2+1,l,r); } bool book[maxn]; vector<int> v[maxn]; int pos[maxn],num[maxn]; int cnt = 1; void dfs(int now,int fa){ pos[now] = cnt++; num[now] = 1; for(int i=0;i<v[now].size();i++){ if(v[now][i]!=fa){ dfs(v[now][i],now); num[now]+=num[v[now][i]]; } } } int n,m; int main() { int T, cas = 1; scanf("%d", &T); while (T--) { cnt = 1; memset(book, false, sizeof(book)); printf("Case #%d:\n", cas++); scanf("%d", &n); for (int i = 1; i <= n; i++) v[i].clear(); m = n - 1; int a,b; while (m--) { scanf("%d%d", &a, &b); v[b].push_back(a); book[a] = true; } for (int i = 1; i <= n; i++) { if (book[i] == false) { dfs(i, 0);//对根节点深搜 break; } } build(1,1,n); scanf("%d", &m); while(m--) { char op[3]; int l,r,k; scanf("%s",&op); if(op[0]=='C') { scanf("%d",&k); query(1,pos[k],pos[k]); } else { scanf("%d %d",&l,&r); change(1,pos[l],pos[l]+num[l]-1,r); } } } return 0; }
