hdu3974-Assign the task(dfs序建线段树)

title: hdu3974-Assign the task(dfs序建线段树)
date: 2019-05-28 15:08:01
categories: ACM
tags: [ACM,算法]

今天做线段树的题碰到一个需要dfs序转化成建线段树，挺有意义的一道题
我的个人博客：https://www.kimiye.xyz

题目描述

There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody’s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.

题目大意

给你一个多叉树，有2种操作，
C x：查询x结点正在做的任务
T x y：给x结点布置y任务
每一次查询要给出一个答案

解题思路

一开始因为是多叉树，没什么区间性，没往线段树上想，就暴力写了一发，给结点染色后，所有子结点也染上色，然后用lazy标记稍稍优化一下，避免重复染色，但还是T了 QAQ

查了一下发现有dfs序建树这种东西，主要用到时间戳(tot)，时间戳以前了解过，很快就上手了

主要思想如下：
对一颗树进行dfs，由于dfs的性质，父亲结点出来的时刻会在儿子结点之后，用l[] , r[]分别表示一个结点进去、出来的时刻，这样从时间戳上看，就形成了一段区间，并且父亲结点是盖住儿子结点的，就可以用线段树求解了~~~
每个结点会产生2个时间戳，所以区间长度是2*n（这边可以优化一下，每个结点产生1个时间戳）
对于更新操作，对l[x]~r[x]执行区间更新
对于查询操作，对l[x]或者r[x]单点查询都可以

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int maxn = 5e4+7;
const int inf = 0x3f3f3f3f;
int T,kase;
int n,m;
vector<int> edge[maxn];
int degree[maxn],tree[8*maxn];
int l[maxn],r[maxn],tot;
// hdu 3974
void dfs(int u)
{
    l[u]=++tot;
    for(int i=0;i<edge[u].size();i++)
        dfs(edge[u][i]);
    r[u]=++tot;
}
void build(int l,int r,int rt)
{
    tree[rt]=-1;
    if(l==r)
        return;
    int mid=(l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}
void pushdown(int rt)
{
    if(tree[rt]!=-1)
    {
        tree[2*rt]=tree[rt];
        tree[2*rt+1]=tree[rt];
        tree[rt]=-1;
    }
}
void update(int L,int R,int y,int l,int r,int rt)
{
    if(L<=l && R>=r)
    {
        tree[rt]=y;
        return;
    }
    pushdown(rt);
    int mid=(l+r)/2;
    if(L<=mid)
        update(L,R,y,l,mid,2*rt);
    if(R>mid)
        update(L,R,y,mid+1,r,2*rt+1);
}
int query(int L,int l,int r,int rt)
{
    if(l==r && l==L)
        return tree[rt];
    pushdown(rt);
    int mid=(l+r)/2;
    if(L<=mid)
        return query(L,l,mid,2*rt);
    else return query(L,mid+1,r,2*rt+1);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        memset(degree,0,sizeof(degree));
        for(int i=0;i<maxn;i++) edge[i].clear();

        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            edge[v].push_back(u);
            degree[u]++;
        }
        int root;
        for(int i=1;i<=n;i++)
            if(!degree[i]) {root=i;break;}
        //printf("rt=%d\n",root);
        dfs(root);
        build(1,2*n,1);
        scanf("%d",&m);
        printf("Case #%d:\n",++kase);
        while(m--)
        {
            char op[3];
            int x,y;
            scanf("%s",op);
            if(op[0]=='C')
            {
                scanf("%d",&x);
                printf("%d\n",query(l[x],1,2*n,1));
            }
            else
            {
                scanf("%d %d",&x,&y);
                update(l[x],r[x],y,1,2*n,1);
            }
        }
    }
    return 0;
}