QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#493073#6163. 消息传递pavement0 0ms0kbC++172.8kb2024-07-26 19:22:332024-07-26 19:22:33

Judging History

你现在查看的是最新测评结果

  • [2024-07-26 19:22:33]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-07-26 19:22:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

int T, n, m, sz[100005], par[100005], dep[100005], anc[25][100005], par_dist[25][100005];
bool vis[100005];
vector<int> adj[100005], all_vec[100005];
vector<ii> chd_vec[100005];

void init(int u, int e = -1) {
	anc[0][u] = e;
	for (int k = 1; k <= 20; k++) {
		if (anc[k - 1][u] == -1) {
			break;
		}
		anc[k][u] = anc[k - 1][anc[k - 1][u]];
	}
	for (auto v : adj[u]) if (v != e) {
		dep[v] = dep[u] + 1;
		init(v, u);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) {
		swap(u, v);
	}
	for (int k = 20; k >= 0; k--) {
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	}
	if (u == v) {
		return u;
	}
	for (int k = 20; k >= 0; k--) {
		if (anc[k][u] != anc[k][v]) {
			u = anc[k][u];
			v = anc[k][v];
		}
	}
	return anc[0][u];
}

int get_sizes(int u, int e = -1) {
	sz[u] = 1;
	for (auto v : adj[u]) if (v != e && !vis[v]) {
		sz[u] += get_sizes(v, u);
	}
	return sz[u];
}

int get_centroid(int u, int tot, int e = -1) {
	for (auto v : adj[u]) if (v != e && !vis[v] && 2 * sz[v] > tot) {
		return get_centroid(v, tot, u);
	}
	return u;
} 

void decomp(int u, int p = -1) {
	int tot = get_sizes(u);
	int c = get_centroid(u, tot);
	par[c] = p;
	vis[c] = 1;
	for (auto v : adj[c]) if (!vis[v]) {
		decomp(v, c);
	}
}

int f(int x, int k) {
	// number of nodes with distance <= k from node x
	int ret = 0;
	for (int cur = x, i = 0, prv = -1; cur != -1; prv = cur, cur = par[cur], i++) {
		int oth = k - par_dist[i][x];
		int all_con = upper_bound(all_vec[cur].begin(), all_vec[cur].end(), oth) - all_vec[cur].begin();
		int chd_con = (prv == -1 ? 0 : upper_bound(chd_vec[cur].begin(), chd_vec[cur].end(), mp(prv, oth)) - lower_bound(chd_vec[cur].begin(), chd_vec[cur].end(), mp(prv, 0)));
		ret += all_con - chd_con;
	}
	return ret;
}

int main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1, u, v; i < n; i++) {
			cin >> u >> v;
			adj[u].pb(v);
			adj[v].pb(u);
		}
		init(1);
		decomp(1);
		for (int i = 1; i <= n; i++) {
			for (int cur = i, k = 0, prv = -1; cur != -1; prv = cur, cur = par[cur], k++) {
				int w = lca(i, cur);
				par_dist[k][i] = dep[i] + dep[cur] - 2 * dep[w];
				all_vec[cur].pb(par_dist[k][i]);
				chd_vec[cur].eb(prv, par_dist[k][i]);
			}
		}
		for (int i = 1; i <= n; i++) {
			sort(all_vec[i].begin(), all_vec[i].end());
			sort(chd_vec[i].begin(), chd_vec[i].end());
		}
		for (int i = 1, x, k; i <= m; i++) {
			cin >> x >> k;
			cout << f(x, k) - f(x, k - 1) << '\n';
		}
	}
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Memory Limit Exceeded

input:

5
10 10
6 3
10 6
2 10
7 2
8 7
1 8
9 1
4 9
5 4
3 2
2 2
8 4
3 5
3 1
8 4
10 1
3 3
10 4
4 3
10 10
3 8
4 3
2 4
6 2
9 6
5 9
1 5
7 1
10 7
4 2
1 3
2 2
6 1
8 5
6 2
10 2
8 4
6 5
6 3
10 10
4 8
2 4
6 2
5 6
1 5
3 1
9 3
7 9
10 7
7 1
10 4
7 3
5 2
6 5
5 1
8 4
8 2
8 3
3 3
10 10
1 10
5 1
4 5
6 4
8 6
9 8
7 9
2 7
3 2
8...

output:

result:

Test #2:

score: 0
Memory Limit Exceeded

input:

5
100 100
30 15
91 30
88 91
9 88
60 9
51 60
71 51
67 71
85 67
36 85
94 36
49 94
33 49
41 33
43 41
17 43
80 17
7 80
59 7
57 59
99 57
8 99
79 8
40 79
21 40
12 21
31 12
18 31
27 18
42 27
93 42
69 93
55 69
66 55
81 66
11 81
29 11
45 29
54 45
58 54
22 58
23 22
89 23
26 89
19 26
53 19
76 53
78 76
56 78
74...

output:

result:

Test #3:

score: 0
Memory Limit Exceeded

input:

5
1000 1000
663 773
549 663
665 549
893 665
276 893
465 276
33 465
327 33
514 327
272 514
251 272
43 251
780 43
280 780
941 280
861 941
638 861
884 638
891 884
51 891
803 51
630 803
439 630
34 439
876 34
109 876
509 109
847 509
31 847
588 31
161 588
683 161
284 683
164 284
255 164
98 255
303 98
49 3...

output:

result:

Test #4:

score: 0
Memory Limit Exceeded

input:

5
60000 60000
1818 5609
3280 5609
38597 1818
12388 1818
56544 3280
55426 3280
52274 38597
33011 38597
51071 12388
38722 12388
57370 56544
49151 56544
35372 55426
23280 55426
23683 52274
54601 52274
18070 33011
42829 33011
15352 51071
15458 51071
58771 38722
11157 38722
43196 57370
32469 57370
55624 ...

output:

3584
254
1504
1008
1984
1920
6144
1792
3584
992
255
3584
1008
254
3840
496
504
7168
992
7168
992
1984
504
254
1984
1920
8192
1984
254
254
254
127
12288
0
504
992
1008
6144
508
1984
496
254
508
6144
3072
7168
1008
12288
504
6144
6144
254
992
504
1984
7168
3840
252
992
1920
3840
508
3584
504
1984
3584...

result:

Test #5:

score: 0
Memory Limit Exceeded

input:

5
80000 80000
32414 16624
30713 16624
60982 32414
42419 32414
79616 30713
22493 30713
33752 60982
15503 60982
12505 42419
66510 42419
3154 79616
39879 79616
3432 22493
71898 22493
5607 33752
53515 33752
48620 15503
57597 15503
64353 12505
47827 12505
79708 66510
11745 66510
27314 3154
26244 3154
794...

output:

3840
3840
992
510
992
992
3840
7168
1984
504
3584
7680
508
3584
992
3584
3840
504
1016
254
508
1504
1920
1920
1920
1920
255
14465
504
12288
255
510
508
1920
1984
1008
3840
7168
508
255
508
992
255
255
3584
255
254
3840
254
7168
508
504
1984
3584
1016
510
508
7168
3840
3584
508
254
3840
1016
6144
508...

result:

Test #6:

score: 0
Memory Limit Exceeded

input:

5
100000 100000
35636 62715
37666 62715
62663 35636
95662 35636
14732 37666
2309 37666
6261 62663
16588 62663
85619 95662
43038 95662
16693 14732
83646 14732
68623 2309
18419 2309
53320 6261
87394 6261
44033 16588
36279 16588
91320 85619
60688 85619
52627 43038
93623 43038
23916 16693
7003 16693
811...

output:

1016
1008
508
508
7168
1984
14336
7680
2016
7680
504
3840
3840
992
7680
3968
1008
7680
1984
3840
1016
14336
3584
9889
1016
2016
5281
1984
1984
1008
1016
8192
12288
24576
12288
7168
3617
3840
254
7168
3840
1984
992
12288
1920
1920
3840
1008
3040
510
1016
1016
255
3840
508
1008
504
508
7168
3584
3840
...

result:

Test #7:

score: 0
Memory Limit Exceeded

input:

5
40000 40000
39296 4358
12021 39296
31954 12021
33108 31954
22734 33108
13356 22734
18060 13356
20061 18060
4490 20061
32858 4490
27375 32858
35460 27375
16186 35460
16531 16186
24421 16531
18324 24421
1238 18324
10375 1238
13626 10375
579 13626
34459 579
25560 34459
32443 25560
27279 32443
9071 27...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

Test #8:

score: 0
Memory Limit Exceeded

input:

5
60000 60000
40941 36220
24488 40941
25598 24488
57464 25598
24717 57464
12405 24717
2878 12405
1705 2878
40647 1705
36886 40647
40100 36886
1374 40100
54679 1374
4847 54679
54317 4847
59816 54317
59093 59816
34501 59093
11685 34501
34152 11685
50526 34152
11944 50526
40569 11944
49415 40569
28999 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

Test #9:

score: 0
Memory Limit Exceeded

input:

5
80000 80000
74308 46405
51588 74308
40653 51588
64228 40653
69268 64228
17874 69268
48184 17874
66467 48184
19044 66467
78853 19044
43302 78853
55227 43302
21132 55227
17436 21132
28310 17436
4170 28310
59967 4170
2170 59967
79810 2170
38942 79810
41090 38942
57890 41090
32329 57890
36758 32329
48...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

Test #10:

score: 0
Memory Limit Exceeded

input:

5
100000 100000
81882 58502
16637 81882
84924 16637
90600 84924
34818 90600
96357 34818
72740 96357
30318 72740
271 30318
21760 271
61595 21760
86375 61595
88541 86375
15421 88541
9149 15421
15177 9149
6210 15177
43626 6210
18657 43626
79496 18657
79065 79496
26397 79065
18154 26397
29404 18154
4437...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:
English 繁體中文 简体中文

Server Time: 2024-12-12 03:50:06 | OpenSource Project