HDU_3974_dfs+线段树

HDU 3974

  • 题意是对以点作为根节点的子树进行操作.恰好可以使用线段树
  • 但是要将每个员工这棵有根树转化成线性区间
  • 开一个标记数组找到根
  • 用dfs转化然后.在对应的区间使用线段树区间修改模板
  • 记得cnt = 0,否则RE
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
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
const int maxn = 50000+5;
vector<int> e[maxn];
bool vis[maxn];
int startp[maxn],endp[maxn];
int add[4*maxn], sum[4*maxn];
int n, m;
int cnt;
void dfs(int index) {
	cnt++;
	startp[index] = cnt;
	for (int i = 0; i < e[index].size(); i++)
		dfs(e[index][i]);
	endp[index] = cnt;
}

void pushDown(int p) {
	if (add[p]) {
		add[2 * p] = add[2 * p + 1] = add[p];
		sum[2 * p] = sum[2 * p + 1] = sum[p];
		add[p] = 0;
	}
}
void change(int L,int R,int p,int left,int right,int val) {
	if (L <= left && right <= R) {
		sum[p] = val;
		add[p] = 1; return;
	}
	pushDown(p);
	int mid = (left + right) / 2;
	if (L <= mid) change(L,R,2*p,left,mid,val);
	if (mid < R) change(L,R,2*p+1,mid+1,right,val);
}
int query(int p,int index,int left,int right) {
	if (left == right) return sum[p];
	int mid = (left + right) / 2;
	pushDown(p);
	if (index <= mid) query(2 * p, index, left, mid);
	else query(2*p+1,index,mid+1,right);
}
int countnum;
int main() {
//	freopen("a.txt","r",stdin);
	int times; cin >> times;
	while (times--) {
		cnt = 0;
		printf("Case #%d:\n",++countnum);
		memset(sum,-1,sizeof sum); //所有人的任务是-1
		memset(add,0,sizeof add); //标记为0
		memset(e,0,sizeof e);
		memset(vis,0,sizeof vis);
		cin >> n;  int a, b;
		for (int i = 1; i <= n - 1; i++) {
			cin >> a >> b;
			e[b].push_back(a);
			vis[a] = 1;
		}
		for (int i = 1; i <= n; i++)
			if (!vis[i]) dfs(i);
		cin >> m; char ch;
		for (int i = 1; i <= m; i++) {
			cin >> ch;
			if (ch == 'C') {
				cin >> a;
				printf("%d\n",query(1,startp[a],1,n));
			}
			else {
				cin >> a >> b;
				change(startp[a],endp[a],1,1,n,b);
			}
		}
	}
	return 0;
}