题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3974
题意：给定点的上下级关系，规定如果给i分配任务a，那么他的所有下属。都停下手上的工作，开始做a。
操作 T x y 分配x任务y，C x询问x的当前任务；
分析：dfs将每个节点以下的子孙节点重新编号映射到一条线段上，再相应地区间修改，单点查询。
#pragma comment(linker,"/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 1000000007 #define inf 0x3f3f3f3f #define N 50010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; struct edge { int v,next; edge(){} edge(int v,int next):v(v),next(next){} }e[N]; int head[N],vis[N],tot; int col[N<<2],num; int st[N],ed[N]; void init() { FILL(head,-1); FILL(vis,0); tot=0; } void addedge(int u,int v) { e[tot]=edge(v,head[u]); head[u]=tot++; } void dfs(int u) { st[u]=++num; for(int i=head[u];~i;i=e[i].next) { dfs(e[i].v); } ed[u]=num; } void build(int l,int r,int rt) { col[rt]=-1; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson); } void Pushdown(int rt) { if(col[rt]!=-1) { col[rt<<1]=col[rt<<1|1]=col[rt]; col[rt]=-1; } } void update(int L,int R,int c,int l,int r,int rt) { if(L<=l&&r<=R) { col[rt]=c; return; } Pushdown(rt); int m=(l+r)>>1; if(L<=m)update(L,R,c,lson); if(m<R)update(L,R,c,rson); } int query(int pos,int l,int r,int rt) { if(l==r)return col[rt]; Pushdown(rt); int m=(l+r)>>1; if(pos<=m)return query(pos,lson); else return query(pos,rson); } int main() { int t,n,m; int a,b,cas=1; char op[10]; scanf("%d",&t); while(t--) { scanf("%d",&n); init(); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); vis[a]=1; addedge(b,a); } num=0; for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); break; } } build(1,num,1); scanf("%d",&m); printf("Case #%d: ",cas++); while(m--) { scanf("%s",op); if(op[0]=='C') { scanf("%d",&a); printf("%d ",query(st[a],1,num,1)); } else { scanf("%d%d",&a,&b); update(st[a],ed[a],b,1,num,1); } } } }