QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812974#72. Mergersguleng2007#10 67ms29080kbC++201.5kb2024-12-13 20:15:412024-12-13 20:15:41

Judging History

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

  • [2024-12-13 20:15:41]
  • 评测
  • 测评结果：10
  • 用时：67ms
  • 内存：29080kb
查看
  • [2024-12-13 20:15:41]
  • 提交

answer

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

const int N=5e5+5;

int fa[N][20], dep[N], cnt[N], ans[N], LCA;
vector <int> g[N], vec[N];

void dfs1(int x)
{
	for(int i=1;i<20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];

	for(auto to:g[x])
		if(to!=fa[x][0])
		{
			dep[to]=dep[x]+1;
			fa[to][0]=x;
			dfs1(to);
		}
}

int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);

	for(int i=19;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];

	if(x==y)
		return x;

	for(int i=19;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i], y=fa[y][i];

	return fa[x][0];
}

void dfs2(int x)
{
	for(auto to:g[x])
		if(to!=fa[x][0])
			dfs2(to), cnt[x] += cnt[to];
}

void dfs3(int x)
{
	for(auto to:g[x])
		if(to!=fa[x][0])
		{
			dfs3(to);
			ans[x] += ans[to];
		}

	if(!cnt[x] && x!=1 && ans[x]==0)
	{
		if(!LCA)
			LCA=x;
		else
			LCA=lca(LCA,x);

		ans[x]++;
	}
}

int main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	dep[1]=1, dfs1(1);

	for(int i=1;i<=n;i++)
	{
		int typ;
		scanf("%d",&typ);
		vec[typ].push_back(i);
	}

	for(int i=1;i<=k;i++)
	{
		if(vec[i].size()==0)
			continue;

		for(int j=0;j<vec[i].size()-1;j++)
			cnt[vec[i][j]]++, cnt[vec[i][j+1]]++, cnt[lca(vec[i][j],vec[i][j+1])] -= 2;
	}

	dfs2(1);
	dfs3(1);

	for(int i=2;i<=n;i++)
		if(dep[i]<dep[LCA] && cnt[i]==0)
		{
			ans[1]++;
			break;
		}

	printf("%d\n",(ans[1]+1)/2);
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 5948kb

input:

1 1
1

output:

0

result:

ok single line: '0'

Test #2:

score: 10
Accepted
time: 2ms
memory: 7912kb

input:

3 2
2 1
3 1
2
2
1

output:

1

result:

ok single line: '1'

Test #3:

score: 10
Accepted
time: 0ms
memory: 7868kb

input:

5 2
1 2
4 5
4 2
3 4
2
1
2
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 10
Accepted
time: 2ms
memory: 5964kb

input:

7 7
5 7
4 7
6 4
1 3
2 6
3 4
6
7
2
4
5
3
1

output:

2

result:

ok single line: '2'

Test #5:

score: 10
Accepted
time: 2ms
memory: 7988kb

input:

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

output:

0

result:

ok single line: '0'

Test #6:

score: 10
Accepted
time: 0ms
memory: 8024kb

input:

100 1
7 97
63 10
65 17
26 85
50 92
92 20
28 83
92 51
5 4
56 2
18 27
16 73
24 78
73 10
35 6
49 10
20 11
42 23
30 7
24 69
38 87
53 45
25 3
93 57
64 47
84 73
20 91
97 31
99 45
20 38
76 9
98 94
40 72
77 38
37 7
88 8
37 78
73 8
90 61
45 68
32 29
55 37
46 88
17 14
46 12
83 100
35 40
71 20
32 92
57 88
92 6...

output:

0

result:

ok single line: '0'

Test #7:

score: 10
Accepted
time: 0ms
memory: 7924kb

input:

100 7
53 48
26 44
28 93
71 74
7 58
76 79
8 89
44 71
80 6
31 67
76 33
90 24
55 1
62 41
95 35
44 68
29 24
18 56
60 85
71 42
71 1
50 78
12 46
67 50
86 50
71 18
17 51
49 13
63 41
2 25
19 93
74 43
74 39
51 43
2 3
61 49
40 61
48 84
99 62
98 43
80 92
58 76
22 43
58 10
50 14
5 26
75 55
19 51
45 38
3 8
23 52...

output:

0

result:

ok single line: '0'

Test #8:

score: 10
Accepted
time: 0ms
memory: 7912kb

input:

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

output:

1

result:

ok single line: '1'

Test #9:

score: 10
Accepted
time: 2ms
memory: 8016kb

input:

100 6
45 58
90 65
28 24
76 32
97 92
50 81
38 17
98 40
81 21
68 56
36 78
45 12
74 31
72 30
20 35
61 85
39 8
69 40
54 60
80 25
5 95
95 27
54 70
19 21
20 12
85 93
16 88
95 48
46 14
45 72
40 7
37 14
72 47
22 10
45 31
75 69
32 6
73 22
56 99
11 35
43 55
1 56
15 56
35 42
100 55
49 34
76 33
87 45
78 70
90 8...

output:

1

result:

ok single line: '1'

Test #10:

score: 10
Accepted
time: 2ms
memory: 5844kb

input:

99 6
44 2
26 24
42 67
94 92
77 97
79 58
50 75
2 12
52 39
30 60
97 94
32 62
12 3
68 8
48 85
18 40
94 37
42 10
7 37
24 12
40 84
41 71
87 49
37 51
22 55
10 9
16 14
52 85
20 86
41 65
69 10
12 55
79 80
50 80
37 16
94 63
93 2
95 31
46 53
65 83
47 9
84 92
4 23
11 98
24 28
54 66
12 72
58 49
40 64
73 39
30 4...

output:

1

result:

ok single line: '1'

Test #11:

score: 10
Accepted
time: 2ms
memory: 7884kb

input:

84 7
10 47
56 65
25 60
13 7
22 55
67 23
30 64
37 12
14 6
55 7
68 66
11 70
65 23
58 56
82 74
3 61
9 29
68 38
80 8
80 5
78 75
75 69
75 31
26 77
18 3
52 49
45 38
6 67
80 26
5 46
39 26
68 40
12 30
14 25
84 21
48 69
43 63
38 36
1 39
12 10
25 31
53 15
74 6
59 30
47 4
32 24
82 33
20 31
44 40
54 38
51 28
32...

output:

2

result:

ok single line: '2'

Test #12:

score: 10
Accepted
time: 0ms
memory: 6012kb

input:

7 7
3 4
7 1
2 1
7 5
5 6
4 6
3
7
2
1
5
4
6

output:

1

result:

ok single line: '1'

Test #13:

score: 10
Accepted
time: 0ms
memory: 5828kb

input:

8 7
6 3
8 1
7 8
1 5
6 7
2 4
3 2
5
4
4
1
3
6
7
2

output:

1

result:

ok single line: '1'

Test #14:

score: 10
Accepted
time: 2ms
memory: 8068kb

input:

100 7
76 43
72 84
5 41
9 38
93 79
11 12
88 52
97 59
69 73
48 49
61 44
17 82
53 55
30 33
87 64
80 37
58 99
53 42
22 36
31 62
88 35
95 75
68 67
29 41
18 84
34 5
1 58
26 14
80 6
1 24
6 36
44 77
55 38
99 9
56 47
45 47
31 13
46 71
61 20
81 3
75 97
39 3
50 60
74 17
66 34
57 95
7 11
8 23
98 28
21 10
22 64
...

output:

0

result:

ok single line: '0'

Test #15:

score: 10
Accepted
time: 2ms
memory: 8048kb

input:

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

output:

1

result:

ok single line: '1'

Test #16:

score: 10
Accepted
time: 2ms
memory: 7884kb

input:

99 6
67 79
71 88
94 20
63 45
56 61
38 83
59 50
21 88
9 51
93 15
54 87
51 36
29 18
24 96
10 25
16 47
5 92
56 45
30 15
22 25
34 1
37 18
38 19
43 76
78 17
61 72
22 64
32 44
52 54
84 3
53 98
42 60
7 89
9 6
92 43
32 66
12 87
4 16
77 10
47 97
33 58
17 35
75 41
23 41
65 26
11 80
7 74
12 79
72 33
97 31
20 5...

output:

1

result:

ok single line: '1'

Test #17:

score: 10
Accepted
time: 2ms
memory: 7924kb

input:

100 6
14 86
25 42
67 97
24 34
12 18
97 31
93 69
1 56
71 100
82 43
55 69
12 33
79 39
88 73
60 62
28 35
21 11
41 89
17 29
63 61
59 75
54 96
13 89
47 58
43 45
50 56
91 74
11 7
20 40
71 94
73 6
38 64
35 23
22 5
93 38
90 54
10 57
23 36
3 22
99 72
74 66
27 18
55 30
9 92
50 78
85 87
26 68
28 60
8 46
44 14
...

output:

1

result:

ok single line: '1'

Test #18:

score: 10
Accepted
time: 2ms
memory: 7968kb

input:

84 7
17 69
82 35
23 65
17 61
57 68
19 40
54 77
10 9
26 11
25 81
19 39
41 71
20 57
28 60
31 83
3 30
31 64
22 52
37 29
38 7
58 59
42 66
66 46
20 25
11 43
71 48
56 51
44 53
76 62
67 21
1 22
46 8
49 33
72 47
38 33
7 70
18 36
43 59
15 9
32 69
30 12
5 4
15 14
8 21
55 39
50 48
41 16
45 4
63 38
24 11
36 12
...

output:

2

result:

ok single line: '2'

Test #19:

score: 10
Accepted
time: 2ms
memory: 5884kb

input:

7 7
7 3
6 3
1 3
4 3
5 3
3 2
7
4
5
6
2
3
1

output:

3

result:

ok single line: '3'

Test #20:

score: 10
Accepted
time: 2ms
memory: 7912kb

input:

15 7
7 9
4 7
7 2
14 7
7 6
7 12
7 3
11 7
7 15
5 7
7 13
8 7
10 7
7 1
7
6
3
4
4
1
3
7
6
3
5
7
2
2
1

output:

1

result:

ok single line: '1'

Test #21:

score: 10
Accepted
time: 0ms
memory: 7932kb

input:

100 7
56 87
56 74
39 56
83 56
99 56
28 56
56 3
56 62
48 56
56 20
24 56
56 17
30 56
11 56
56 40
73 56
56 61
56 6
56 16
2 56
56 94
19 56
56 85
56 70
56 68
57 56
56 75
53 56
56 1
56 59
71 56
47 56
55 56
56 31
80 56
93 56
56 66
14 56
56 76
56 97
56 89
35 56
56 49
12 56
56 82
58 56
100 56
95 56
9 56
56 4...

output:

0

result:

ok single line: '0'

Test #22:

score: 10
Accepted
time: 2ms
memory: 5944kb

input:

8 7
6 8
8 7
4 1
8 2
8 3
8 5
4 8
1
6
5
2
7
4
1
3

output:

2

result:

ok single line: '2'

Test #23:

score: 10
Accepted
time: 2ms
memory: 7928kb

input:

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

output:

1

result:

ok single line: '1'

Test #24:

score: 10
Accepted
time: 2ms
memory: 8032kb

input:

100 7
92 59
94 51
14 84
73 15
38 90
62 7
19 29
71 87
17 80
64 28
16 35
42 20
80 13
38 9
89 50
92 72
97 50
18 38
17 98
95 58
14 23
57 94
68 28
55 76
95 45
1 15
3 41
36 58
34 64
28 49
34 53
66 41
49 57
21 69
62 76
48 60
43 80
99 16
50 41
78 22
20 77
56 57
49 47
9 51
26 97
64 79
69 42
76 97
33 75
45 34...

output:

0

result:

ok single line: '0'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #25:

score: 24
Accepted
time: 3ms
memory: 8544kb

input:

3000 1500
1639 2173
2404 1870
1283 985
2883 2977
707 1329
2113 636
2806 2624
298 1064
2713 2778
1794 1869
1414 707
123 438
2461 1887
1110 2119
1348 508
2262 230
1447 938
730 421
328 2137
323 2423
2777 2620
2884 2449
638 662
2399 1045
1371 1573
2756 1439
2580 622
13 2700
1415 997
1276 83
480 30
413 2...

output:

130

result:

ok single line: '130'

Test #26:

score: 0
Wrong Answer
time: 4ms
memory: 8500kb

input:

3000 2999
307 2061
703 217
101 1823
2902 2612
784 2034
2721 2411
1613 746
2392 33
2494 2005
2428 1620
2075 677
97 581
1813 2279
468 565
1348 801
117 2390
2392 2869
1176 1082
2775 2376
1759 51
1752 2287
2021 612
1496 2060
15 2805
1006 1517
2800 2233
1761 2915
296 2685
452 2544
2725 269
347 986
2939 3...

output:

751

result:

wrong answer 1st lines differ - expected: '752', found: '751'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #66:

score: 22
Accepted
time: 46ms
memory: 25988kb

input:

100000 100000
14957 4585
67467 70858
61843 47396
50630 17382
61027 39858
94990 21698
10240 22940
23505 67581
91432 14182
22040 40125
24556 60351
75822 41519
82801 23601
90653 29138
85096 34582
99587 59109
8932 45189
18235 36632
43160 14939
67600 76675
60175 65542
99294 53955
46429 66931
16822 48854
...

output:

25042

result:

ok single line: '25042'

Test #67:

score: 22
Accepted
time: 58ms
memory: 26124kb

input:

100000 50000
3065 28396
57666 99424
91431 92279
85107 9397
40557 2609
33754 76986
41982 13262
29268 57814
57080 70949
46008 55628
16881 69517
7925 97656
11194 27261
1023 44957
63053 94265
10347 36227
57858 50853
6707 37237
14023 64077
97278 89836
45448 37054
47530 12666
1789 54939
97196 38225
46942 ...

output:

4686

result:

ok single line: '4686'

Test #68:

score: 22
Accepted
time: 62ms
memory: 23708kb

input:

100000 1000
15892 97873
74044 8515
2591 62904
30957 88449
38848 47109
51265 48273
55368 54375
67431 61662
74306 32695
87126 54432
72682 57299
66802 28200
3201 72387
26153 31276
44001 47337
27981 6477
15995 26102
90218 8030
97876 99025
38725 79748
61045 12996
27173 63491
31237 7298
64134 63770
59955 ...

output:

252

result:

ok single line: '252'

Test #69:

score: 22
Accepted
time: 64ms
memory: 24764kb

input:

100000 50000
33160 23295
28957 34869
60520 32863
7862 68797
48379 81124
95012 36902
86480 11178
89023 90581
98753 45510
95 163
50395 60900
89762 36279
56185 22354
15359 97979
61728 37941
68183 27192
52885 40031
54463 33490
22324 25911
44115 5401
62127 25301
91088 99953
1770 73224
78624 45860
87886 2...

output:

4466

result:

ok single line: '4466'

Test #70:

score: 22
Accepted
time: 60ms
memory: 29080kb

input:

100000 100000
55749 64307
73914 18165
55104 67680
34976 24633
3159 10270
97438 41767
63073 69455
57888 71630
93066 38126
39516 27458
45215 74459
19402 17568
91414 23901
84838 44332
86229 23656
41101 30330
35829 54890
34576 52494
61355 23809
68784 29220
60951 22840
14091 80771
98672 67030
55873 80581...

output:

1

result:

ok single line: '1'

Test #71:

score: 22
Accepted
time: 66ms
memory: 24512kb

input:

100000 10000
30268 39315
46960 33279
28973 55390
22427 61537
60481 79337
30617 20845
59764 27962
17169 39537
65704 18355
51311 86246
34879 31926
90444 83548
94519 80339
98171 79780
79228 94164
91379 44847
97383 90313
45917 64737
22007 66486
49018 7172
90191 31105
80577 48727
26092 3821
9302 17496
60...

output:

2509

result:

ok single line: '2509'

Test #72:

score: 22
Accepted
time: 67ms
memory: 22600kb

input:

100000 1000
11983 6879
71457 57412
57580 56139
50216 34933
12061 84340
23054 62561
94774 46880
55255 30380
38271 57910
59277 70810
80275 32460
39997 11027
70416 43264
1617 86814
15261 89577
12622 88741
16344 80224
10682 4096
73248 12167
99850 50822
16526 23109
40141 86110
91267 35155
16588 24615
385...

output:

250

result:

ok single line: '250'

Test #73:

score: 22
Accepted
time: 38ms
memory: 24712kb

input:

100000 50000
1644 78388
28413 1644
1644 85336
34228 1644
1644 17492
44196 1644
1644 81781
1644 48872
1644 13725
1644 11683
1644 81789
1644 331
88941 1644
24119 1644
16646 1644
28572 1644
1644 86432
1644 65072
51344 1644
82782 1644
1644 29259
1644 55827
82183 1644
1644 51814
1644 61332
23306 1644
164...

output:

9226

result:

ok single line: '9226'

Test #74:

score: 0
Wrong Answer
time: 48ms
memory: 25224kb

input:

100000 100000
75311 62863
12992 62863
62863 84650
62863 51354
62863 26895
62863 45506
73949 62863
52325 62863
82731 62863
62863 69152
62863 90856
32788 62863
55788 62863
62863 27200
62863 57738
62863 31
62863 23706
62863 66045
56818 62863
62863 67848
62863 29291
62863 76276
62863 64266
73 62863
2299...

output:

49999

result:

wrong answer 1st lines differ - expected: '50000', found: '49999'

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2025-01-20 05:55:21 | OpenSource Project