HDU3974Assign the task(DFS序+线段树)

/*
translation:一个公司里面每个员工都有一个顶头上司，一旦给某个员工分配任务后，这个员工以及该员工的所有下属都在做该任务。有若干操作，分配给员工任务以及查询该员工正在执行的任务。
solution:线段树，时间戳一般化很明显该公司的所有员工间的关系可以用一颗多叉树来表示。然后就是dfs给这棵树打上时间戳。根据新分配的id号码将其节点对应映射到线段树上面。这样分配任务就相当与更新一段连续的节点，查询任务相当与单点查询。
*/
#include<bits/stdc++.h>
using namespace std;
#define N 50010
struct Edge
{int to, nxt;Edge(){};Edge(int _to, int _nxt):to(_to), nxt(_nxt){};
}edge[N];
struct SegTree
{int l, r, val, lazy;
}seg[N<<2];
int head[N], start[N], en[N], tol, cnt;
bool used[N];
void init()
{tol=cnt=0;memset(head, -1, sizeof(head));
}
void addedge(int u, int v)
{edge[tol]=Edge(v, head[u]);head[u]=tol++;
}
void dfs(int u)
{++cnt;start[u]=cnt;for(int i=head[u]; i!=-1; i=edge[i].nxt){dfs(edge[i].to);}en[u]=cnt;
}
void build(int l, int r, int rt)
{seg[rt].l=l;seg[rt].r=r;seg[rt].val=-1;seg[rt].lazy=0;if(l==r) return ;int mid=(l+r)>>1;build(l, mid, rt<<1);build(mid+1, r, rt<<1|1);
}
void pushdown(int rt)
{if(seg[rt].lazy){seg[rt].lazy=0;seg[rt<<1].val=seg[rt<<1|1].val=seg[rt].val;seg[rt<<1].lazy=seg[rt<<1|1].lazy=1;}
}
void update(int rt, int l, int r, int val)
{if(l<=seg[rt].l&&r>=seg[rt].r){seg[rt].val=val;seg[rt].lazy=1;return ;}pushdown(rt);int mid=(seg[rt].l+seg[rt].r)>>1;if(r<=mid) update(rt<<1, l, r, val);else if(l>mid) update(rt<<1|1, l, r, val);else{update(rt<<1, l, mid, val);update(rt<<1|1, mid+1, r, val);}
}
int query(int rt, int u)
{if(seg[rt].l==u&&seg[rt].r==u) return seg[rt].val;pushdown(rt);int mid=(seg[rt].l+seg[rt].r)>>1;if(u<=mid) return query(rt<<1, u);else return query(rt<<1|1, u);
}
int main()
{int T, u, v, n, m;scanf("%d", &T);for(int kase=1; kase<=T; kase++){init();memset(used, false, sizeof(used));scanf("%d", &n);for(int i=1; i<n; i++){scanf("%d%d", &u, &v);used[u]=true;addedge(v, u);}for(int i=1; i<=n; i++)if(!used[i]){dfs(i);break;}build(1, cnt, 1);char op[10];scanf("%d", &m);printf("Case #%d:\n", kase);while(m--){scanf("%s", op);if(op[0]=='C'){scanf("%d", &u);printf("%d\n", query(1, start[u]));}else{scanf("%d%d", &u, &v);update(1, start[u], en[u], v);}}}return 0;
}