洛谷P3066 [USACO12DEC]Running Away From the Barn G 题解

发表于 | 分类于

题意：
给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于等于l的点有多少个。

挺有意思的啊这道题

设x节点在dfs序中的位置是 $dfn_x$ ，以它为根的子树大小为 $size_x$ 。

那么这个子树内节点的 $dfn$ 值一定位于区间 $[dfn_x, dfn_x + size_x)$ 内。

这样就把问题转化成了区间第 $k$ 大的问题，用主席树维护即可。 

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	int tmp = 0;
	char c = getchar();
	while(!is_digit(c)) c = getchar();
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp;
}

inline ll readll() {
	ll tmp = 0;
	char c = getchar();
	while(!is_digit(c)) c = getchar();
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp;
}

inline void write(int x) {
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

struct edge {
	int t, nxt;
	ll v;
} e[400010];

int head[200010], p, dfn[200010], sz[200010], n, q, d[200010], c, L[9000010], R[9000010];
int siz[9000010], root[200010], N;
ll depth[200010], qwq[200010], l; 

inline void add_edge(int s, int t, ll v) {
	p++;
	e[p].t = t;
	e[p].v = v;
	e[p].nxt = head[s];
	head[s] = p;
}

void dfs(int x, int fa) {
	q++;
	sz[x] = 1;
	dfn[x] = q;
	d[q] = x;
	for(register int i = head[x]; i; i = e[i].nxt) {
		if(e[i].t == fa) continue ;
		depth[e[i].t] = depth[x] + e[i].v; 
		dfs(e[i].t, x);
		sz[x] += sz[e[i].t];
	}
}

void build(int &rt, int l, int r, int p) {
	rt = ++c;
	siz[rt] = 1;
	if(l == r) return ;
	int mid = (l + r) >> 1;
	// cout << l << " " << r << " " << mid << endl;
	// system("pause");
	if(p <= mid) build(L[rt], l, mid, p);
	else build(R[rt], mid + 1, r, p);
}

void modify(int &rt, int rt1, int l, int r, int p) {
	rt = ++c;
	L[rt] = L[rt1];
	R[rt] = R[rt1];
	siz[rt] = siz[rt1] + 1;
	if(l == r) return ;
	int mid = (l + r) >> 1;
	if(p <= mid) modify(L[rt], L[rt1], l, mid, p);
	else modify(R[rt], R[rt1], mid + 1, r, p);
}

int query(int rt, int l, int r, int p) {
	if(r <= p) return siz[rt];
	int mid = (l + r) >> 1;
	if(p <= mid) {
		if(L[rt]) return query(L[rt], l, mid, p);
		else return 0;
	} else {
		int res = 0;
		if(L[rt]) res += siz[L[rt]];
		if(R[rt]) res += query(R[rt], mid + 1, r, p);
		return res;
	}
}

int main() {
	n = read(), l = readll();
	for(register int i = 2; i <= n; i++) {
		int s = read(); ll t = readll();
		add_edge(s, i, t);
		add_edge(i, s, t);
	}
	dfs(1, 0);
	for(register int i = 1; i <= n; i++) {
		qwq[i] = depth[i];
	}
	sort(qwq + 1, qwq + n + 1);
	N = unique(qwq + 1, qwq + n + 1) - (qwq + 1);
	build(root[0], 1, N, 1);
	for(register int i = 1; i <= n; i++) {
		// cout << d[i] << " " << i << " " << depth[d[i]] << endl;
		int p = lower_bound(qwq + 1, qwq + N + 1, depth[d[i]]) - qwq;
		modify(root[i], root[i - 1], 1, N, p);
	}
	for(register int i = 1; i <= n; i++) {
		int p = upper_bound(qwq + 1, qwq + N + 1, depth[i] + l) - qwq - 1;
		write(query(root[dfn[i] + sz[i] - 1], 1, N, p) - query(root[dfn[i] - 1], 1, N, p)),
		putchar(10);
	}
	return 0;
}