ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202977 | #3525. 车窗外 这夜色 流光溢彩 | one_zero_three_zero | 100 | 9033ms | 84084kb | C++11 | 1.2kb | 2024-02-18 09:58:42 | 2024-02-18 12:31:02 |
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,m,t,maxn;
int u,v;
bool vis[1000005];
int cnt[1000005];
long long dp[1000005];
int fa[1000005];
int h[1000005];
vector<int> a[1000005];
void erg(int u,int dep){
h[u] = dep;
if(vis[u]){
cnt[u] = 1;
maxn = max(maxn,dep);
}
for(auto && i : a[u]){
if(i == fa[u]) continue;
fa[i] = u;
erg(i,dep + 1);
cnt[u] += cnt[i];
}
}
void dfs(int u){
for(auto && i : a[u]){
if(i == fa[u]) continue;
dfs(i);
dp[u] += dp[i];
if(cnt[i] == 0) continue;
dp[u] += 2;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("../data.in","r",stdin);
freopen("../data.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;i ++){
scanf("%d",&t);
vis[t] = 1;
}
for(int i = 1;i < n;i ++){
scanf("%d %d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
erg(1,0);
dfs(1);
printf("%lld\n",dp[1] - maxn);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 24736kb
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: 24728kb
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: 0ms
memory: 24732kb
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: 8ms
memory: 24728kb
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: 7ms
memory: 24732kb
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: 4ms
memory: 24732kb
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: 0ms
memory: 24728kb
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: 8ms
memory: 24732kb
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: 3ms
memory: 24732kb
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: 4ms
memory: 24732kb
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: 4ms
memory: 25020kb
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: 13ms
memory: 24996kb
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: 4ms
memory: 25012kb
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: 8ms
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: 11ms
memory: 25028kb
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: 14ms
memory: 24996kb
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: 10ms
memory: 25012kb
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: 13ms
memory: 24996kb
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: 4ms
memory: 25028kb
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: 4ms
memory: 24996kb
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: 741ms
memory: 80628kb
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: 959ms
memory: 76604kb
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: 787ms
memory: 83108kb
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: 970ms
memory: 76604kb
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: 748ms
memory: 84084kb
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: 969ms
memory: 77572kb
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: 835ms
memory: 83792kb
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: 1022ms
memory: 77572kb
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: 818ms
memory: 83232kb
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: 1062ms
memory: 77576kb
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