HDU 3974

本来想熟悉下线段树，只是题目叙述没能理解为什么和线段树相关。
看了别人的思路，想要将问题搜索过程做优化，就需要人为排序，同时这个排序还能一定程度反映这种树节点的父子关系，因此先使用DFS定义一个顺序

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int INF= 0x3f3f3f3f;
const int maxn= 5e4+5;

struct Node
{
	int lz, jb;
	Node(int zz= 0, int nn= -1)
		: lz(zz), jb(nn) {}
}tr[maxn<<2];
int be[maxn], en[maxn];
int tot;
bool vis[maxn];
vector<int> G[maxn];
int cop[maxn];

inline void AddEdge(int u, int v)
{
	G[v].push_back(u);
}
void Init(int n)
{
	memset(vis, 0, sizeof(vis));
	for (int i= 1; i <= n; ++i){
		G[i].clear();
	}
}
void dfs(int x)
{
	be[x]= ++tot;
	int sz= G[x].size();
	// cop[tot]= x;
	for (int i= 0; i < sz; ++i){
		dfs(G[x][i]);
	}
	en[x]= tot;
}
void Build(int x, int l, int r)
{
	tr[x]= Node(0, -1);
	if (l >= r){
		return;
	}
	int mid= (l+r)>>1, ch= x<<1;
	Build(ch, l, mid);
	ch|= 1;
	Build(ch, mid+1, r);
}
void PushD(int fa, int l, int r)
{
	if (!tr[fa].lz){
		return;
	}

	if (l >= r){
		return;
	}

	int ch= fa<<1;
	tr[ch].jb= tr[fa].jb;
	tr[ch].lz= 1;
	ch|= 1;
	tr[ch].jb= tr[fa].jb;
	tr[ch].lz= 1;
}
void PushU(int fa, int l, int r)
{
	if (l >= r){
		return;
	}

	if (tr[fa<<1].jb != tr[fa<<1|1].jb){
		tr[fa].jb= -1;
	} else{
		tr[fa].jb= tr[fa<<1].jb;
	}
}
void Update(int x, int l, int r, int L, int R, int v)
{
	if (l > r){
		return;
	}
	if (L <= l && R >= r){
		tr[x].jb= v;
		tr[x].lz= 1;
		return;
	}

	PushD(x, l, r);
	tr[x].lz= 0;

	int mid= (l+r)>>1;
	if (mid >= L){
		Update(x<<1, l, mid, L, R, v);
	}
	if (mid < R){
		Update(x<<1|1, mid+1, r, L, R, v);
	}

	PushU(x, l, r);
}
int Query(int pos, int x, int l, int r)
{
	if (l == r || -1 != tr[x].jb){
		return tr[x].jb;
	}

	int mid= (l+r)>>1;
	if (mid >= pos){
		return Query(pos, x<<1, l, mid);
	} else{
		return Query(pos, x<<1|1, mid+1, r);
	}

}

int main()
{
	int T, n, m;
	scanf("%d", &T);

	for (int kase= 1; kase <= T; ++kase){
		scanf("%d", &n);
		Init(n);
		int u, v;
		for (int i= 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			vis[u]= 1;
			AddEdge(u, v);
		}

		tot= 0;
		for (int i= 1; i <= n; ++i){
			if (!vis[i]){
				dfs(i);
			}
		}

		Build(1, 1, n);
		scanf("%d", &m);

		int jb, x;
		int q;
		char op;
		printf("Case #%d:
", kase);
		while (m--){
			scanf(" %c", &op);
			if ('C' == op){
				scanf("%d", &x);
				q= Query(be[x], 1, 1, n);
				printf("%d
", q);
			} else{
				scanf("%d%d", &x, &jb);
				Update(1, 1, n, be[x], en[x], jb);
			}
		}
	}
}