题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3974
给你T组数据，n个节点，n-1对关系，右边的是左边的父节点，所有的值初始化为-1，然后给你q个操作：
有两种操作：
操作一：T X Y ，将以X为根的子树上的所有节点都变成Y。
操作二：C X，查询第X号点是多少？
没想到是线段树做，就算想到了也想不到用dfs序做...
例子中给你了这样的树：
2
/ \
3 5
/ \
4 1
DFS一遍转化成DFS序：2344113552
然后记录下每个数字最左边和最右边的位置，如：left[3] = 2, right[3] = 7。
因为是DFS序，所以他的子节点的范围一定包含在他的左右位置中。
所以就变成了很明显的线段树成段更新...
注意一点的是，查询是单点更新...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + ;
const int INF = 1e9 + ;
struct segtree {
int l , r , val , lazy;
}T[MAXN << ];
struct data {
int next , to;
}edge[MAXN];
int head[MAXN] , cont , L[MAXN] , R[MAXN];
//链式前向星
inline void add(int u , int v) {
edge[cont].to = v;
edge[cont].next = head[u];
head[u] = cont++;
}
//DFS序
void dfs(int u) {
L[u] = min(L[u] , ++cont);
R[u] = max(R[u] , cont);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
dfs(v);
}
L[u] = min(L[u] , ++cont);
R[u] = max(R[u] , cont);
} void init(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].lazy = ;
if(l == r) {
T[p].val = -;
return ;
}
init(p << , l , mid);
init((p << )| , mid + , r);
} void updata(int p , int l , int r , int val) {
int mid = (T[p].l + T[p].r) >> ;
if(l == T[p].l && T[p].r == r) {
T[p].val = val;
T[p].lazy = val;
return ;
}
if(T[p].lazy) {
T[p << ].val = T[(p << )|].val = T[p << ].lazy = T[(p << )|].lazy = T[p].lazy;
T[p].lazy = ;
}
if(r <= mid) {
updata(p << , l , r , val);
}
else if(l > mid) {
updata((p << )| , l , r , val);
}
else {
updata(p << , l , mid , val);
updata((p << )| , mid + , r , val);
}
} int query(int p , int index) {
int mid = (T[p].l + T[p].r) >> ;
if(index == T[p].l && T[p].r == index) {
return T[p].val;
}
if(T[p].lazy) {
T[p << ].val = T[(p << )|].val = T[p << ].lazy = T[(p << )|].lazy = T[p].lazy;
T[p].lazy = ;
}
if(index <= mid) {
return query(p << , index);
}
else {
return query((p << )| , index);
}
} int main()
{
int t , n , u , v , root , q;
char str[];
scanf("%d" , &t);
for(int ca = ; ca <= t ; ca++) {
scanf("%d" , &n);
cont = , root = (n + ) * n / ;
for(int i = ; i <= n ; i++) {
R[i] = head[i] = -;
L[i] = INF;
}
for(int i = ; i < n ; i++) {
scanf("%d %d" , &u , &v);
root -= u;
add(v , u);
}
cont = ;
dfs(root);
init( , , cont);
printf("Case #%d:\n" , ca);
scanf("%d" , &q);
while(q--) {
scanf("%s" , str);
if(str[] == 'T') {
scanf("%d %d" , &u , &v);
updata( , L[u] , R[u] , v);
}
else {
scanf("%d" , &u);
printf("%d\n" , query( , L[u]));
}
}
}
}