题目链接：https://vjudge.net/problem/HDU-3974
知识点： 线段树、DFS
题目大意：
公司中有(N)个职员，一个职员对应一个上司，这(N)个职员刚好组成一棵树。当给一个职员(x)分配任务(y)时（即 (T) (x) (y))，(x)及其下属及其下属的下属都会放下手头的工作去完成任务(y)。对于每次询问（即(C) (x)），程序输出职员(x)正在进行什么任务。
解题思路：
先将公司中职员之间的关系抽象成一棵树，每次分配任务其实就是更新一棵子树。当我们按(DFS)遍历的顺序为一棵子树编号时，我们会发现它们是连续的一串数字。于是我们可以先给整棵树用(DFS)序编号。每次更新任务其实就是更新一串连续数字对应的职员的当前任务，这就可以用线段树来处理了；而查询职员的当前任务其实就是线段树的单点查询。
AC代码：
1 #include <cstdio> 2 #include <vector> 3 4 using namespace std; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 8 const int maxn = 50005; 9 vector<int> son[maxn]; 10 bool root[maxn]; 11 int cnt; 12 int lef[maxn],rit[maxn]; 13 int now[maxn<<2]; 14 bool lazy[maxn<<2]; 15 16 void dfs(int rt){ 17 cnt++; 18 lef[rt]=cnt; 19 for(int i=0;i<son[rt].size();i++) 20 dfs(son[rt][i]); 21 rit[rt]=cnt; 22 } 23 void pushdown(int rt){ 24 now[rt<<1]=now[rt<<1|1]=now[rt]; 25 lazy[rt<<1]=lazy[rt<<1|1]=true; 26 lazy[rt]=false; 27 } 28 void build(int l,int r,int rt){ 29 now[rt]=-1; 30 lazy[rt]=false; 31 if(r==l) return; 32 int m=(l+r)>>1; 33 build(lson); 34 build(rson); 35 } 36 void update(int L,int R,int c,int l,int r,int rt){ 37 if(l!=r&&lazy[rt]) pushdown(rt); 38 if(L==l&&R==r){ 39 now[rt]=c; 40 lazy[rt]=true; 41 return; 42 } 43 int m=(l+r)>>1; 44 if(m>=L) update(L,min(m,R),c,lson); 45 if(m<R) update(max(L,m+1),R,c,rson); 46 } 47 int query(int pos,int l,int r,int rt){ 48 if(l!=r&&lazy[rt]) pushdown(rt); 49 if(l==r) return now[rt]; 50 int m=(l+r)>>1; 51 if(m>=pos) return query(pos,lson); 52 else return query(pos,rson); 53 } 54 int main() 55 { 56 int T,N,M,x,y,u,v; 57 scanf("%d",&T); 58 for(int t=1;t<=T;t++){ 59 printf("Case #%d: ",t); 60 scanf("%d",&N); 61 for(int i=1;i<=N;i++){ 62 root[i]=true; 63 son[i].clear(); 64 } 65 for(int i=1;i<N;i++){ 66 scanf("%d%d",&u,&v); 67 son[v].push_back(u); 68 root[u]=false; 69 } 70 cnt=0; 71 for(int i=1;i<=N;i++){ 72 if(root[i]){ 73 dfs(i); 74 break; 75 } 76 } 77 build(1,cnt+1,1); 78 79 scanf("%d",&M); 80 char ord[5]; 81 for(int i=0;i<M;i++){ 82 scanf("%s",ord); 83 if(ord[0]=='C'){ 84 scanf("%d",&x); 85 printf("%d ",query(lef[x],1,cnt+1,1)); 86 } 87 else{ 88 scanf("%d%d",&x,&y); 89 update(lef[x],rit[x],y,1,cnt+1,1); 90 } 91 } 92 } 93 return 0; 94 }