HDU3974 Assign the task（多叉树转换为线段+线段树区间染色）

题目大意：有n个人，给你他们的关系（老板和员工），没有直属上司的人就是整个公司的领导者，这意味着n个人形成一棵树(多叉树)。当一个人被分配工作时他会让他的下属也做同样的工作（并且立即停止手头正在做的工作），题目会询问你其中某个人正在做的工作。

解题思路：其实从“一个人分配他的下属做一样的工作”这里就可以看出来了，这相当于让一块区间的人都做一样的事，就是线段树区间染色问题。但不能使用线段树，要先将多叉树铺展开，将节点映射到线段上。把每个人的管理区段找出来（把属于同一个人管的放一起，上司放在前面），这样对某个员工更新也就是对他和他下属的更新。具体实现就是先将多叉树保存下来，用dfs遍历多叉树给每个人打上时间戳，分配序号就行了。

 #include<iostream>

 #include<cstring>

 #include<vector>

 #define LC(a) ((a<<1))

 #define RC(a) ((a<<1)+1)

 #define MID(a,b) ((a+b)>>1)

 using namespace std;

 const int N=5e4+;

 typedef long long ll;

 vector<ll>v[N];

 ll Start[N],End[N];//每个员工所有下属的开始和结束节点，包含本身

 ll ans,cnt;//cnt用于记录节点的编号

 bool used[N];

 void dfs(ll rt){

     Start[rt]=++cnt;

     for(int i=;i<v[rt].size();i++){

         dfs(v[rt][i]);

     }

     End[rt]=cnt;

 }

 struct node{

     ll l,r;

     ll task;//task=-2表示下属工作不同

 }tree[N*];

 void pushup(ll p){

     tree[p].task=(tree[LC(p)].task==tree[RC(p)].task?tree[LC(p)].task:-);

 }

 void pushdown(ll p){

     tree[LC(p)].task=tree[RC(p)].task=tree[p].task;

 }

 void build(ll p,ll l,ll r){

     tree[p].l=l;

     tree[p].r=r;

     tree[p].task=-;

     if(l==r){

         return;

     }

     build(LC(p),l,MID(l,r));

     build(RC(p),MID(l,r)+,r);

 }

 void update(ll p,ll l,ll r,ll task){

     if(r<tree[p].l||l>tree[p].r)

         return;

     if(l<=tree[p].l&&r>=tree[p].r){

         tree[p].task=task;

         return;

     }

     if(tree[p].task!=-)

         pushdown(p);

     update(LC(p),l,r,task);

     update(RC(p),l,r,task);

     pushup(p);

 }

 void query(ll p,ll t){

     if(tree[p].task!=-){

         ans=tree[p].task;

         return;

     }

     ll mid=MID(tree[p].l,tree[p].r);

     if(t<=mid)

         query(LC(p),t);

     else

         query(RC(p),t);

 }

 int main(){

     ios::sync_with_stdio(false);

     ll t;

     ll cas=;

     cin>>t;

     while(t--){

         cas++;

         //初始化

         cnt=;

         memset(used,false,sizeof(used));

         for(int i=;i<=N;i++){

             v[i].clear();

         }

         ll n;

         cin>>n;

         for(int i=;i<=n-;i++){

             ll    rt,chd;

             cin>>chd>>rt;

             used[chd]=true;

             v[rt].push_back(chd);

         }

         //将多叉树转化为线段

         for(int i=;i<=n;i++){

             //找到根结点

             if(!used[i]){

                 dfs(i);

                 break;

             }

         }

         //建树

         build(,,n);

         ll m;

         cout<<"Case #"<<cas<<":"<<endl;

         cin>>m;

         for(int i=;i<=m;i++){

             char op;

             cin>>op;

             if(op=='C'){

                 ll x,t;

                 cin>>x;

                 t=Start[x];

                 query(,t);

                 cout<<ans<<endl;

             }

             else{

                 ll x,l,r,task;

                 cin>>x>>task;

                 l=Start[x];

                 r=End[x];

                 update(,l,r,task);

             }

         }

     }

 }