20190829模拟赛 圣诞树

发表于 更新于 分类于

$Problem’s$ $Website$

圣诞树

（没有权限查看题目的同学不要打我）

这是一道经典题，我们首先用类似链剖分的方法求一个dfs序，将树上问题转化为线性问题，用两个数组记录每一棵子树起始的dfs序和终止的dfs序，然后处理每个赋颜色的操作，记录每个操作最后一个起始子树的dfs序（因为可能重复赋值），然后将所有子树按照终止子树的dfs序升序排序，维护一个类似指针的东西，表示当前的颜色，先枚举子树根，如果当前颜色起始的dfs序在这棵子树中，就在那个位置$+1$，如果这种颜色有重复赋值，我们就在它上一个赋值的位置$-1$，最后对于每个子树区间，树状数组加一下就是答案，有点像 差分前缀和 。

$Code$

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
//Coded by dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
inline int sc() {
	int xx = 0, ff = 1; char cch = gc;
	while(!isdigit(cch)) {
		if(cch == '-') ff = -1; cch = gc;
	}
	while(isdigit(cch)) {
		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
	}
	return xx * ff;
}
inline void out(int x) {
	if(x < 0)
		pc('-'), x = -x;
	if(x >= 10)
		out(x / 10);
	pc(x % 10 + '0');
}
#define re register
using std :: sort;
const int Maxn = 1e5 + 10;
struct TREE {
	int nxt, to;
}t[Maxn << 1];
struct SON {
	int l, r, id;
	bool operator < (const SON &x) const {
		return r < x.r;
	}
}q[Maxn];
struct COLOR {
	int p, c, lst;
	bool operator < (const COLOR &x) const {
		return p < x.p;
	}
}a[Maxn];
int n, m, cnt;
int head[Maxn], ta[Maxn], ans[Maxn], now[Maxn], st[Maxn], ed[Maxn];
inline void ADD(int from, int to) {
	t[++cnt].nxt = head[from];
	t[cnt].to = to;
	head[from] = cnt;
}
inline void dfs(int id) {
	st[id] = ++cnt;
	for(re int i = head[id]; i; i = t[i].nxt) {
		int to = t[i].to;
		if(!st[to])
			dfs(to);
	}
	ed[id] = cnt;
}
#define lowbit(i) (i & (-i))
inline void update(int x, int z) {
	for(; x <= n; x += lowbit(x))
		ta[x] += z;
}
inline int query(int x) {
	int res = 0;
	for(; x; x -= lowbit(x))
		res += ta[x];
	return res;
}
int main() {
	while(scanf("%d%d", &n, &m) != EOF) {
		//init
		cnt = 0;
		memset(head, 0, sizeof(head));
		memset(st, 0, sizeof(st));
		memset(ed, 0, sizeof(ed));
		memset(ta, 0, sizeof(ta));
		memset(now, 0, sizeof(now));
		for(re int i = 1; i < n; ++i) {
			int x = sc(), y = sc();
			ADD(x, y), ADD(y, x);
		}
		cnt = 0;
		dfs(1);
		for(re int i = 1; i <= m; ++i) {
			int x = sc(), y = sc();
			a[i].p = st[x], a[i].c = y;
		}
		sort(a + 1, a + m + 1);
		for(re int i = 1; i <= m; ++i) {
			a[i].lst = now[a[i].c];
			now[a[i].c] = a[i].p;
		}
		for(re int i = 1; i <= n; ++i) {
			q[i] = SON{st[i], ed[i], i};
		}
		sort(q + 1, q + n + 1);
		int top = 0;
		for(re int i = 1; i <= n; ++i) {
			while(top < m && a[top + 1].p <= q[i].r) {
				++top;
				update(a[top].p, 1);
				if(a[top].lst)
					update(a[top].lst, -1);
			}
			ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
		}
		for(re int i = 1; i <= n; ++i)
			out(ans[i]), pc(' ');
		pc('\n');
	}
	return 0;
}

$rp++$