HDU 3974 Assign the task（DFS序）题解

题意：给出一棵树，改变树的一个节点的值，那么该节点及所有子节点都变为这个值。给出m个询问。

思路：DFS序，将树改为线性结构，用线段树维护。start[ ]记录每个节点的编号，End[ ]为该节点的最小子节点的编号，维护线段树时，即是维护start[x] 到End[x]。

代码：

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 50000+5;

const int MOD = 20071027;

using namespace std;

vector<int> g[N];

int tot,start[N],End[N],a[N<<2],vis[N];

void init(){

	for(int i = 0; i < N; i++) g[i].clear();

	memset(vis,0,sizeof(vis));

	tot = 0;

}

void add(int u,int v){	// u is boss

	g[u].push_back(v);

	vis[v] = 1;

}

void dfs(int x){

	start[x] = ++tot;

	int len = g[x].size();

	for(int i = 0; i < len; i++){

		int v = g[x][i];

		dfs(v);

	}

	End[x] = tot;

}

void build(int rt,int l,int r){

	if(l == r){

		a[rt] = -1;

		return;

	}

	int m = (l + r) >> 1;

	build(rt<<1,l,m);

	build(rt<<1|1,m+1,r);

	a[rt] = -1;

}

void push_down(int rt){

	if(a[rt] != -1){

		a[rt<<1] = a[rt<<1|1] = a[rt];

		a[rt] = -1;

	}

}

void update(int rt,int l,int r,int L,int R,int v){

	if(L <= l && R >=r){

		a[rt] = v;

		return;

	}

	push_down(rt);

	int m = (l + r) >> 1;

	if(L <= m) update(rt<<1,l,m,L,R,v);

	if(R > m) update(rt<<1|1,m+1,r,L,R,v);

}

int query(int rt,int l,int r,int x){

	if(l == r){

		return a[rt];

	}

	if(a[rt] != -1){

		return a[rt];

	}

	int ans;

	int m = (l + r) >> 1;

	if(x <= m) ans = query(rt<<1,l,m,x);

	else ans = query(rt<<1|1,m+1,r,x);

	return ans;

}

int main(){

	int T,n,u,v,m,num = 1;

	char order[2];

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		init();

		for(int i = 0; i < n-1; i++){

			scanf("%d%d",&v,&u);

			add(u,v);

		}

		for(int i = 1; i <= n; i++){

			if(!vis[i]){

				dfs(i);

				break;

			}

		}

		build(1,1,n);

		scanf("%d",&m);

		printf("Case #%d:\n",num++);

		while(m--){

			scanf("%s",order);

			if(order[0] == 'C'){

				scanf("%d",&u);

				printf("%d\n",query(1,1,n,start[u]));

			}

			else{

				scanf("%d%d",&u,&v);

				update(1,1,n,start[u],End[u],v);

			}

		}

	}

    return 0;

}