题目大意：公司里有一些员工及对应的上级，给出一些员工的关系，分配给某员工任务后，其和其所有下属都会进行这项任务。输入T表示分配新的任务，
输入C表示查询某员工的任务。本题的难度在于建树，一开始百思不得其解，后来看了lx大大的博客后才明白，用递归建立了各个员工之间的关系，Start[x]
表示x员工为Boss的起点,End[x]表示x员工为Boss的终点。之后对这样的整体线段进行赋值即可。
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define N 50005
struct tree
{
int l, r, task, iscover;
int mid()
{
return (l+r)/;
}
}a[N<<];
int vis[N], index, Start[N], End[N];
vector<int>G[N];
void dfs(int k)///模拟为boss树，记录各员工在树上的编号
{
Start[k] = ++index;
for(int i=, len=G[k].size(); i<len; i++)
dfs(G[k][i]); End[k] = index;
}
void build(int rt, int l, int r)
{
a[rt].l = l;
a[rt].r = r;
a[rt].task = -;
a[rt].iscover = ;
if(l==r)return ;
build(lson, l, a[rt].mid());
build(rson, a[rt].mid()+, r);
}
void Down(int rt)
{
if(a[rt].l!=a[rt].r && a[rt].iscover)
{
a[lson].iscover = a[rson].iscover = ;
a[rt].iscover = ;
a[lson].task = a[rson].task = a[rt].task;
}
}
void Update(int rt, int l, int r, int task)
{
if(a[rt].l==l && a[rt].r==r)
{
a[rt].task = task;
a[rt].iscover = ;
return ;
} Down(rt); if(a[rt].mid()>=r)Update(lson, l, r, task);
else if(a[rt].mid()<l)Update(rson, l, r, task);
else
{
Update(lson, l, a[rt].mid(), task);
Update(rson, a[rt].mid()+, r, task);
}
}
int Query(int rt, int k)
{
if(a[rt].l==a[rt].r)
{
return a[rt].task;
} Down(rt); if(a[rt].mid()>=k)return Query(lson, k);
else return Query(rson, k);
}
int main()
{
int T, icase = ;
scanf("%d", &T);
while(T--)
{
int n, b, c;
memset(vis, , sizeof(vis));
scanf("%d", &n);
for(int i=; i<=n; i++)
G[i].clear();
for(int i=; i<n; i++)
{
scanf("%d %d", &b, &c);
G[c].push_back(b);
vis[b] = ;
}
index = ;
for(int i=; i<=n; i++)
{
if(!vis[i])
{
dfs(i);///找到最高BOSS
break;
}
}
build(, , n);
int m, x, y;
scanf("%d", &m);
char order[];
printf("Case #%d:\n", icase++);
while(m--)
{
scanf("%s", order);
if(order[]=='T')
{
scanf("%d %d", &x, &y);
Update(, Start[x], End[x], y);
}
else
{
scanf("%d", &x);
printf("%d\n", Query(, Start[x]));
}
}
}
return ;
}