HDU3974 (Assign the task)[DFS序，线段树]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3974

乍一看是要维护一颗树节点的颜色，每次要修改一整颗子树的颜色。但如果把这棵树的DFS序（这里用的先序遍历）写出来，就可以发现每次维护的颜色都是一段连续DFS序上的，用线段树维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
const int MAXN=50009;
const int MIX=1000000009;
int fa[MAXN];
vector<int> V[MAXN];
int ff=0;
int l[MAXN];
int r[MAXN];
int cnt=0;

int t=2;

struct Node {
	int col,nc;
	int lc,rc;
}v[MAXN*4];

void build(int now,int l,int r) {
	v[now].col=-1;
	v[now].nc=-1;
	if(l<r-1) {
		int mid=(l+r)>>1;
		v[now].lc=t;
		build(t++,l,mid);
		v[now].rc=t;
		build(t++,mid,r);
	}
	else {
		v[now].lc=v[now].rc=0;
	}
}

void update(int now,int l,int mid,int r) {
	if(v[now].nc==-1) return ;
	v[v[now].lc].nc=v[now].nc;
	v[v[now].rc].nc=v[now].nc;
	v[v[now].lc].col=v[now].nc;
	v[v[now].rc].col=v[now].nc;
	v[now].nc=-1;
}

void change(int now,int l,int r,int lr,int rr,int nc) {
	if(lr<=l&&r<=rr) {
		v[now].nc=nc;
		v[now].col=nc;
		return ;
	}
	int mid=(l+r)>>1;
	if(v[now].nc!=-1) update(now,l,mid,r);
	if(lr<mid) change(v[now].lc,l,mid,lr,rr,nc);
	if(mid<rr) change(v[now].rc,mid,r,lr,rr,nc);
	if(v[v[now].lc].col==MIX || v[v[now].rc].col==MIX) v[now].col=MIX;
	else if(v[v[now].lc].col==v[v[now].rc].col) v[now].col=v[v[now].lc].col;
	else v[now].col=MIX;
}

int _ans=-1;
void query(int now,int l,int r,int lr) {
	if(l>=r) return ;
	if(v[now].col!=MIX) {
		_ans=v[now].col;
		return ;
	}
	int mid=(l+r)>>1;
	if(v[now].nc!=-1) update(now,l,mid,r);
	if(lr<mid) query(v[now].lc,l,mid,lr);
	if(mid<lr+1) query(v[now].rc,mid,r,lr);
}

int root=1;

void dfs(int x) {
	l[x]=++cnt;
	r[x]=0;
	for(int i=0;i<V[x].size();i++) {
		dfs(V[x][i]);
		r[x]=max(r[x],r[V[x][i]]);
	}
	if(r[x]==0) r[x]=cnt;
}

int n;
int main() {
	int T;
	int x,y;
	char s[10];
	scanf("%d",&T);
	for(int c=1;c<=T;c++) {
		printf("Case #%d:\n",c);
		scanf("%d",&n);
		cnt=0;
		memset(fa,0,sizeof(fa));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(int i=0;i<=n;i++) V[i].clear();
		for(int i=1;i<n;i++) {
			scanf("%d%d",&x,&y);
			fa[x]=y;
			V[y].push_back(x);
		}
		for(int i=1;i<=n;i++) {
			if(fa[i]==0) {
				ff=i;
				break;
			}
		}
		dfs(ff);
		t=2;
		build(root,0,cnt+1);
		int m;
		scanf("%d",&m);
		for(int i=0;i<m;i++) {
			scanf("%s",s);
			if(s[0]=='C') {
				scanf("%d",&x);
				_ans=-1;
				query(root,0,cnt+1,l[x]);
				printf("%d\n",_ans);
			}
			else if(s[0]=='T') {
				scanf("%d%d",&x,&y);
				change(root,0,cnt+1,l[x],r[x]+1,y);
			}
		}
	}
}