ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202971 | #3525. 车窗外 这夜色 流光溢彩 | smallstone | 100 | 8555ms | 101588kb | C++11 | 929b | 2024-02-18 09:41:33 | 2024-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