HDU 3974 Assign the task（简单线段树）

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.

For each test case:

The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.

The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).

The next line contains an integer M (M ≤ 50,000).

The following M lines each contain a message which is either

"C x" which means an inquiry for the current task of employee x

or

"T x y"which means the company assign task y to employee x.

(1<=x<=N,0<=y<=10^9)

/* ***********************************************
Author :kuangbin
Created Time :2013-11-17 19:50:24
File Name :E:\2013ACM\比赛练习\2013-11-17\C.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; const int MAXN = ;
struct Edge
{
int to,next;
}edge[MAXN];
int head[MAXN],tot;
int cnt;
int start[MAXN],end[MAXN];
void init()
{
cnt = ;
tot = ;
memset(head,-,sizeof(head));
}
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u)
{
++cnt;
start[u] = cnt;
for(int i = head[u];i != -;i = edge[i].next)
{
dfs(edge[i].to);
}
end[u] = cnt;
}
struct Node
{
int l,r;
int val;
int lazy;
}segTree[MAXN*];
void Update_Same(int r,int v)
{
if(r)
{
segTree[r].val = v;
segTree[r].lazy = ;
}
}
void push_down(int r)
{
if(segTree[r].lazy)
{
Update_Same(r<<,segTree[r].val);
Update_Same((r<<)|,segTree[r].val);
segTree[r].lazy = ;
}
}
void Build(int i,int l,int r)
{
segTree[i].l = l;
segTree[i].r = r;
segTree[i].val = -;
segTree[i].lazy = ;
if(l == r)return;
int mid = (l+r)/;
Build(i<<,l,mid);
Build((i<<)|,mid+,r);
}
void update(int i,int l,int r,int v)
{
if(segTree[i].l == l && segTree[i].r == r)
{
Update_Same(i,v);
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/;
if(r <= mid)update(i<<,l,r,v);
else if(l > mid)update((i<<)|,l,r,v);
else
{
update(i<<,l,mid,v);
update((i<<)|,mid+,r,v);
}
}
int query(int i,int u)
{
if(segTree[i].l == u && segTree[i].r == u)
return segTree[i].val;
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/;
if(u <= mid)return query(i<<,u);
else return query((i<<)|,u);
}
bool used[MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
int T;
scanf("%d",&T);
int iCase = ;
while(T--)
{
iCase++;
printf("Case #%d:\n",iCase);
int u,v;
memset(used,false,sizeof(used));
init();
scanf("%d",&n);
for(int i = ;i < n;i++)
{
scanf("%d%d",&u,&v);
used[u] = true;
addedge(v,u);
}
for(int i = ;i <= n;i++)
if(!used[i])
{
dfs(i);
break;
}
Build(,,cnt);
char op[];
int m;
scanf("%d",&m);
while(m--)
{
scanf("%s",op);
if(op[] == 'C')
{
scanf("%d",&u);
printf("%d\n",query(,start[u]));
}
else
{
scanf("%d%d",&u,&v);
update(,start[u],end[u],v);
}
}
}
return ;
}