hdu3974 Assign the task線段樹 dfs序

題意：

無序的給編號為1-n的員工安排上下級，

操作一：給一個員工任務C，則該員工以及他的下級任務都更換為任務C

操作二：詢問一個員工，返回他的任務

 

題解:

給一個員工任務，則他所在組都要改變，聯想到線段樹的區間修改，但是這裡是對一個人操作，不是區間操作，如果能把“點”操作變成“區間”操作責問題就轉化為區間修改和單點查詢問題了，這裡用dfs序把原狀態的點對映到一條線上去

 

dfs序：

找到一個沒有父親的點

按照下圖求出他的l和r，每次進入的時候都加一，返回的時候不加

編號     1 2 3 4 5

左端點 4 1 3 5 2

右端點 4 5 5 5 2

即2號點他左端到1，右端到5

 

 

單點查詢：

查詢x，則可以理解為查詢l[x]或r[x]（下屬和自己的工作一致）

區間修改：

比如上圖改變2即改變1,5

 

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e5+90;
  4 const int inf=1e9+90;
  5 #define eps 1e-10
  6 #define forn(i,n) for(int i=0;i<n;i++)
  7 #define form(i,n) for(int i=1;i<=n;i++)
  8 typedef long long ll ;
  9 typedef unsigned long long ull ;
 10 #define ls l,mid,p<<1
 11 #define rs mid+1,r,p<<1|1
 12 int a[N];
 13 int n,m,root,rt;
 14 int to[N],ver[N],h[N],tot;
 15 char c[2];
 16 void add(int x,int y){
 17     to[++tot]=h[x];
 18     ver[tot]=y;
 19     h[x]=tot;
 20 }
 21 struct Node{
 22     int l,r;
 23     ll sum;
 24 }t[N<<2];
 25 int ml[N],mr[N];
 26 void dfs(int x){
 27     //進來的時候+1，
 28     ml[x]=++rt;
 29     for(int i=h[x];~i;i=to[i]){
 30         dfs(ver[i]);
 31     }
 32     mr[x]=rt;//返回的時候不需要+1
 33 }
 34 void pd(int p){
 35     if(t[p].sum!=-1){
 36         t[p<<1].sum=t[p<<1|1].sum=t[p].sum;
 37         t[p].sum=-1;
 38     }
 39 }
 40 void build(int l,int r,int p){
 41     if(l==r){
 42         t[p].l=t[p].r=l;
 43         t[p].sum=-1;
 44         return;
 45     }
 46     t[p]={l,r,-1};
 47     int mid=l+r>>1;
 48     build(l,mid,p<<1);
 49     build(mid+1,r,p<<1|1);
 50 }
 51 void modify(int l,int r,int c,int p){
 52     if(l<=t[p].l&&t[p].r<=r){
 53         t[p].sum=c;
 54         return;
 55     }
 56     pd(p);
 57     int mid=t[p].l+t[p].r>>1;
 58     if(l<=mid)modify(l,r,c,p<<1);
 59     if(r>mid)modify(l,r,c,p<<1|1);
 60 }
 61 int query(int x,int p){
 62     if(t[p].l==t[p].r)return t[p].sum;
 63     pd(p);
 64     int mid=t[p].l+t[p].r>>1;
 65     int ans=-1;
 66     if(x<=mid)ans=query(x,p<<1);
 67     else ans=query(x,p<<1|1);
 68     return ans;
 69 }
 70 int main(){
 71 //    freopen("in.txt","r",stdin);
 72 //    freopen("out.txt","w",stdout);
 73     int T,x,y;
 74     cin>>T;
 75     form(k,T){
 76         printf("Case #%d:\n",k);
 77         scanf("%d",&n);
 78         memset(a,0,sizeof(a));
 79         memset(h,-1,sizeof(h));
 80         tot=0,rt=0;
 81         forn(i,n-1) {
 82             scanf("%d%d", &x, &y);
 83             add(y,x);
 84             a[x] = 1;
 85         }
 86         form(i,n){
 87             if(!a[i]){
 88                 root=i;
 89                 break;
 90             }
 91         }
 92         scanf("%d",&m);
 93         dfs(root);
 94         build(1,n,1);
 95         forn(i,m){
 96             scanf("%s",c);
 97             if(c[0]=='C'){
 98                 scanf("%d",&x);
 99                 printf("%d\n",query(ml[x],1));
100             }else{
101                 scanf("%d%d",&x,&y);
102                 modify(ml[x],mr[x],y,1);
103             }
104         }
105     }
106 }