UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202971#3525. 车窗外 这夜色 流光溢彩smallstone1008555ms101588kbC++11929b2024-02-18 09:41:332024-02-18 12:30:49

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define N 1000010
ll n, m, k, p[N], val[2][N], fa[N], sz[N];
vector<ll> g[N];
void add(int u, int v){
	g[u].push_back(v);
}
void dfs(int u, int f){
	for(auto v : g[u]){
		if(f == v)
			continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
}
void dfs2(int u, int f){
	for(auto v : g[u]){
		if(f == v || !sz[v])
			continue;
		dfs2(v, u);
		val[1][u] += val[1][v] + 2;
	}
	val[0][u] = val[1][u];
	for(auto v : g[u]){
		if(f == v || !sz[v])
			continue;
		val[0][u] = min(val[0][u], val[1][u] - 1 - val[1][v] + val[0][v]);
	}
}
int main(){
	scanf("%lld%lld", &n, &m);
	for(int i = 1 ; i <= m ; i++){
		scanf("%lld", p + i);
		sz[p[i]]++;
	}
	for(int i = 1 ; i < n ; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 1);
	dfs2(1, 1);
	printf("%lld", val[0][1]);
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 11ms
memory: 24696kb

input:

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

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 3ms
memory: 24692kb

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #4:

score: 0
Accepted
time: 0ms
memory: 24688kb

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 3ms
memory: 24688kb

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 0ms
memory: 24692kb

input:

5 9
4 2 3 5 1 0 0 0 0
5 4
2 4
1 5
3 5

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 4ms
memory: 24692kb

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #8:

score: 0
Accepted
time: 0ms
memory: 24696kb

input:

6 8
4 3 6 2 5 1 0 0
6 2
5 2
1 6
3 6
4 1

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 7ms
memory: 24688kb

input:

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

output:

12

result:

ok 1 number(s): "12"

Test #10:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 0ms
memory: 25044kb

input:

4996 15
3964 3029 1403 4476 2880 3132 2415 1901 4817 3331 1232 1414 2254 401 2545
4250 1566
821 1566...

output:

855

result:

ok 1 number(s): "855"

Test #12:

score: 0
Accepted
time: 11ms
memory: 25000kb

input:

4997 512
4033 651 4512 646 2737 377 1672 4149 3949 776 3966 241 1677 4612 1028 2485 2449 1618 1852 4...

output:

2569

result:

ok 1 number(s): "2569"

Test #13:

score: 0
Accepted
time: 8ms
memory: 25032kb

input:

5000 960
800 4614 587 2573 4864 2880 611 3419 702 2067 1616 2539 2826 599 205 2388 2876 3768 4698 25...

output:

4994

result:

ok 1 number(s): "4994"

Test #14:

score: 0
Accepted
time: 4ms
memory: 24996kb

input:

4996 196
3368 4332 2571 1682 1827 1941 3598 3164 289 2166 2999 3388 4456 3036 1447 3979 1942 3820 23...

output:

1277

result:

ok 1 number(s): "1277"

Test #15:

score: 0
Accepted
time: 3ms
memory: 25064kb

input:

4997 1670
2081 2936 2340 3478 4319 206 3890 2022 852 4974 2512 4642 4487 391 2335 1005 2053 4929 209...

output:

5942

result:

ok 1 number(s): "5942"

Test #16:

score: 0
Accepted
time: 13ms
memory: 25028kb

input:

4996 4532
4599 770 1111 3946 4537 57 2671 4342 2118 4091 2427 1021 3940 875 251 1722 1633 550 3087 3...

output:

9521

result:

ok 1 number(s): "9521"

Test #17:

score: 0
Accepted
time: 4ms
memory: 25052kb

input:

4998 3253
279 2476 4104 1766 1416 274 2471 4442 308 1610 3800 1338 4646 1099 1743 1492 1776 4448 241...

output:

8046

result:

ok 1 number(s): "8046"

Test #18:

score: 0
Accepted
time: 3ms
memory: 25000kb

input:

5000 683
509 898 2709 3838 1922 2803 107 3007 536 660 284 2343 997 4928 4449 4417 3420 604 2 638 197...

output:

3135

result:

ok 1 number(s): "3135"

Test #19:

score: 0
Accepted
time: 8ms
memory: 25080kb

input:

4998 4406
4756 3228 4083 2427 543 912 2483 298 2229 2963 2024 4530 3998 4701 1288 4081 1981 2776 245...

output:

8695

result:

ok 1 number(s): "8695"

Test #20:

score: 0
Accepted
time: 3ms
memory: 25024kb

input:

4996 4041
3262 4271 2855 234 2106 3362 470 2826 3891 2705 3533 1645 1871 2807 4339 1370 303 47 601 4...

output:

8938

result:

ok 1 number(s): "8938"

Subtask #3:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 636ms
memory: 90472kb

input:

999997 1
609695
738478 594839
317328 594839
201435 594839
580977 594839
440742 738478
304787 580977
...

output:

40593

result:

ok 1 number(s): "40593"

Test #22:

score: 0
Accepted
time: 758ms
memory: 70052kb

input:

1000000 1
952552
243709 679245
653887 679245
609827 679245
681973 679245
34205 681973
951892 34205
2...

output:

24

result:

ok 1 number(s): "24"

Test #23:

score: 0
Accepted
time: 635ms
memory: 93768kb

input:

999995 1
217420
630267 364824
720204 364824
871920 720204
870371 720204
625951 364824
163720 364824
...

output:

97003

result:

ok 1 number(s): "97003"

Test #24:

score: 0
Accepted
time: 777ms
memory: 70044kb

input:

999996 1
389900
940443 191238
140630 191238
63551 940443
985771 140630
778819 985771
448938 191238
3...

output:

24

result:

ok 1 number(s): "24"

Test #25:

score: 0
Accepted
time: 619ms
memory: 95084kb

input:

999996 1
514095
869056 600885
844857 600885
909976 844857
671491 909976
651232 671491
548725 651232
...

output:

57631

result:

ok 1 number(s): "57631"

Subtask #4:

score: 50
Accepted

Test #26:

score: 50
Accepted
time: 1054ms
memory: 89888kb

input:

999996 563443
695404 211314 551983 316474 937862 38389 747185 3258 737288 354968 158575 571013 63181...

output:

1480363

result:

ok 1 number(s): "1480363"

Test #27:

score: 0
Accepted
time: 877ms
memory: 101588kb

input:

1000000 745426
558698 478713 172317 999443 332691 877210 37327 431001 666697 739190 500934 440505 56...

output:

1650442

result:

ok 1 number(s): "1650442"

Test #28:

score: 0
Accepted
time: 1069ms
memory: 90784kb

input:

999995 678416
587427 520855 825924 996298 759521 359824 827243 699190 523039 475401 472819 873193 59...

output:

1636865

result:

ok 1 number(s): "1636865"

Test #29:

score: 0
Accepted
time: 819ms
memory: 97696kb

input:

999996 365402
530718 946843 136010 419613 401117 590144 570477 859767 409307 359647 138508 32732 818...

output:

1251915

result:

ok 1 number(s): "1251915"

Test #30:

score: 0
Accepted
time: 1206ms
memory: 91912kb

input:

999995 822057
312794 128807 350384 546108 796929 79650 85378 695458 499809 259281 485039 528948 8083...

output:

1810476

result:

ok 1 number(s): "1810476"

Extra Test:

score: 0
Extra Test Passed