题意：给定点的上下级关系，规定如果给i分配任务a，那么他的所有下属。都停下手上的工作，开始做a。

操作 T x y 分配x任务y，C x询问x的当前任务；

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深度优先遍历重新编号，使一个结点的儿子连续。然后成段更新。

2：1-5

5：2-2<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+M6O6My01PC9wPgo8cD4xo7o0LTQ8L3A+CjxwPjSjujUtNTwvcD4KPHA+PGJyPgo8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include #include #include #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define N 50001 using namespace std; int lazy[N<<2]; int task[N<<2]; int next[N],pre[N],to[N]; int uset[N]; int num; int l[N],r[N]; int find_set(int x) { while(uset[x]!=x) x=uset[x]; return x; } void dfs(int root) { int i=pre[root]; l[root]=(++num); while(i!=-1) { dfs(to[i]); i=next[i]; } r[root]=num; } void pushdown(int rt) { if(lazy[rt]!=-1) { task[rt<<1]=lazy[rt]; lazy[rt<<1]=lazy[rt]; task[rt<<1|1]=lazy[rt]; lazy[rt<<1|1]=lazy[rt]; lazy[rt]=-1; } } void build(int l,int r,int rt) { task[rt]=-1; lazy[rt]=-1; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void update(int L,int R,int l,int r,int rt,int val) { if(L<=l&&r<=R) { lazy[rt]=val; task[rt]=val; return; } pushdown(rt); int m=(r+l)>>1; if(L<=m) update(L,R,lson,val); if(R>m) update(L,R,rson,val); } void query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { printf("%d\n",task[rt]); return; } pushdown(rt); int m=(l+r)>>1; if(L<=m) query(L,R,lson); if(R>m) query(L,R,rson); } int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { int n; int u,v; scanf("%d",&n); for(int i=1;i<=n;i++) { uset[i]=i; pre[i]=-1; } for(int i=1;i