The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
InputThe first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
"C x" which means an inquiry for the current task of employee x
or
"T x y"which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)OutputFor each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.Sample Input
1
5
4 3
3 2
1 3
5 2
5
C 3
T 2 1
C 3
T 3 2
C 3
Sample Output
Case #1:
-1
1
2 用dfs序来把这棵树化成线性的结构，然后线段树的单点修改和区间查询即可 用Start和End记录每个点所代表区间的起点和终点
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int head[maxn], Start[maxn], End[maxn], flag[maxn];
int a, b, x, y, ans, cnt, ret; struct node{
int l, r, w, f;
}Node[maxn*]; struct dot{
int v, next;
}Dot[maxn]; void add(int u, int v)
{
Dot[ret].v = v;
Dot[ret].next = head[u];
head[u] = ret++;
} void dfs(int u)
{
++cnt;
Start[u] = cnt;
for(int i=head[u]; i!=-; i=Dot[i].next)
dfs(Dot[i].v);
End[u] = cnt;
} void build(int k, int ll, int rr)
{
Node[k].l = ll, Node[k].r = rr;
Node[k].w = -;
Node[k].f = ;
if(ll == rr) return;
int m = (ll + rr) / ;
build(k*, ll, m);
build(k*+, m+, rr);
} void down(int k)
{
Node[k*].f = Node[k].f;
Node[k*+].f = Node[k].f;
Node[k*].w = Node[k].f;
Node[k*+].w = Node[k].f;
Node[k].f = ;
} void qp(int k)
{
if(Node[k].l == Node[k].r)
{
ans = Node[k].w;
return;
}
if(Node[k].f) down(k);
int m = (Node[k].l + Node[k].r) / ;
if(a <= m) qp(k*);
else qp(k*+);
} void chinter(int k)
{
if(Node[k].l >= a && Node[k].r <= b)
{
Node[k].w = y;
Node[k].f = y;
return;
}
if(Node[k].f) down(k);
int m = (Node[k].l + Node[k].r) / ;
if(a <= m) chinter(k*);
if(b > m) chinter(k*+);
} int main()
{
int T, kase = ;
scanf("%d",&T);
while(T--)
{
mem(head, -);
mem(flag, -);
mem(Start, -);
mem(End, -);
mem(Dot, );
mem(flag, -);
ret = ;
cnt = ;
int n, m, se;
printf("Case #%d:\n",++kase);
scanf("%d",&n);
for(int i=; i<n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
flag[u] = v;
se = v;
add(v, u);
}
while(flag[se] != -)
se = flag[se];
dfs(se);
build(, , cnt);
scanf("%d",&m);
char str[];
getchar();
for(int i=; i<m; i++)
{
scanf("%s",str);
if(strcmp(str, "C") == )
{
int p;
ans = -;
scanf("%d",&p);
a = Start[p];
qp();
printf("%d\n",ans);
}
else if(strcmp(str, "T") == )
{
scanf("%d%d", &x, &y);
a = Start[x];
b = End[x];
chinter();
}
} } return ;
}