HDU 3974 (dfs序+线段树)

题意： 一个公司内共 $n$n个人，给出这 $n$n个人的上下级关系。一个人下属的下属也是他的下属。当一个人被分配了新的工作时，他的所有下属也将被分配这个新的工作(所有下属停止当前做的工作开始做新的工作)。每个人初始的工作为 $-1$−1， $m$m次操作每次要么查询编号为 $x$x人正在做的工作，要么更新一个人要做的工作(他的所有下属工作也将被更新)。

题解： $dfs$dfs序求出一个人所有的下属，然后线段树区间更新单点查询即可。
忘初始化无限 $RE$RE，血和泪的教训~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 5e5 + 10, M = N;
int T, n, m;

bool isfa[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int siz[N], dfn[N], tim;
void dfs(int u) {
	dfn[u] = ++tim;
	siz[u] = 1;
	for(int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		siz[u] += siz[j];
	}
}

struct Node{
	int l, r;
	int task, add;
}tr[N << 2];

void pushdown(int u) {
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if(root.add != -1) {
		left.task = left.add = root.add;
		right.task = right.add = root.add;
		root.add = -1;
	}
}

void build(int u, int l, int r) {
	tr[u] = {l, r, -1, -1};
	if(l == r) return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);	
}

void modify(int u, int l, int r, int task) {
	if(tr[u].l >= l && tr[u].r <= r) {
		tr[u].task = tr[u].add = task;
		return ;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) modify(u << 1, l, r, task);
	if(r > mid) modify(u << 1 | 1, l, r, task);
}

int query(int u, int x) {
	if(tr[u].l == tr[u].r) return tr[u].task;
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) return query(u << 1, x);
	return query(u << 1 | 1, x);
}

void init(){
	idx = 0, tim = 0;
	memset(h, -1, sizeof h);
	memset(isfa, true, sizeof isfa);
}

int main()
{
	scanf("%d", &T);
	for(int k = 1; k <= T; k++) {
		printf("Case #%d:\n", k);
		
		init();
		scanf("%d", &n);
		for(int i = 1; i < n; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(b, a);
			isfa[a] = false;
		}
		
		int root = 0;
		for(int i = 1; i <= n; i++) 
			if(isfa[i]) {root = i; break;}
		
		dfs(root); 
		
		build(1, 1, n);
		
		scanf("%d", &m);
		while(m--) {
			char op[2]; int x, y;
			scanf("%s%d", op, &x);
			if(*op == 'C') printf("%d\n", query(1, dfn[x]));
			else {
				scanf("%d", &y);
				modify(1, dfn[x], dfn[x] + siz[x] - 1, y);
			}
		}
	}
	return 0;
}