HDU 3974 Assign the task（dfs时间戳+线段树成段更新）

题意：给定点的上下级关系，规定假设给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深度优先遍历又一次编号。使一个结点的儿子连续。

然后成段更新。

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY29kZV9vcl9jb2Rl/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" height="146" width="302">

代码：

#include<iostream>

#include<cstdio>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define read_ freopen("i.txt","r",stdin)

using  namespace std;

const int N=50010;

int task[N<<2],lazy[N<<2];

struct node{

        int to,next;

}edge[N];

int ll;

int l[N],r[N];

int uset[N],adj[N];

int num;

void addedge(int u,int v)

{

        edge[ll].to=u;

        edge[ll].next=adj[v];

        adj[v]=ll++;

}

void dfs(int root)

{

        int i=adj[root];

        l[root]=(++num);

        while(i!=-1)

        {

                dfs(edge[i].to);

                i=edge[i].next;

        }

        r[root]=num;

}

void pushdown(int rt)

{

        if(lazy[rt]!=-1)

        {

                task[rt<<1]=lazy[rt];

                task[rt<<1|1]=lazy[rt];

                lazy[rt<<1]=lazy[rt];

                lazy[rt<<1|1]=lazy[rt];

                lazy[rt]=-1;

        }

}

int find_set(int x)

{

        if(uset[x]!=x)

                uset[x]=find_set(uset[x]);

        return uset[x];

}

void build_tree(int l,int r,int rt)

{

        task[rt]=-1;

        lazy[rt]=-1;

        if(l==r)

                return;

        int m=(l+r)>>1;

        build_tree(lson);

        build_tree(rson);

}

void update(int L,int R,int val,int l,int r,int rt)

{

        if(L<=l&&r<=R)

        {

                task[rt]=val;

                lazy[rt]=val;

                return;

        }

        pushdown(rt);

        int m=(l+r)>>1;

        if(L<=m) update(L,R,val,lson);

        if(R>m) update(L,R,val,rson);

}

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()

{

        //read_;

        int T;

        scanf("%d",&T);

        for(int cas=1;cas<=T;cas++)

        {

                int n;

                scanf("%d",&n);

                ll=0;

                num=0;

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

                {

                        adj[i]=-1;

                        uset[i]=i;

                }

                int u,v;

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

                {

                        scanf("%d%d",&u,&v);

                        uset[u]=v;

                        addedge(u,v);

                }

                int root=find_set(1);

                dfs(root);

                build_tree(1,num,1);

                int m;

                scanf("%d",&m);

                char op[5];

                int a,b;

                printf("Case #%d:\n",cas);

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

                {

                        scanf("%s",op);

                        if(op[0]=='C')

                        {

                                scanf("%d",&a);

                                query(l[a],l[a],1,num,1);

                        }

                        else{

                                scanf("%d%d",&a,&b);

                                update(l[a],r[a],b,1,num,1);

                        }

                }

        }

        return 0;

}