UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202977#3525. 车窗外 这夜色 流光溢彩one_zero_three_zero1009033ms84084kbC++111.2kb2024-02-18 09:58:422024-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