UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213509#2769. 覆盖WZRYWZWY10040310ms300288kbC++111.3kb2024-11-12 19:08:492024-11-12 23:07:27

answer

#include<bits/stdc++.h> // https://blog.csdn.net/weixin_41100093/article/details/87857685
//菜到只会用原题了 
using namespace std;
const int maxn = 2e6+5;
int n, m;
set<int>Q[maxn];
vector<int>M[maxn];
vector<int>res;
int ans[maxn], tot = 0;
void dfs(int u, int fa){
    for(int i=0;i<M[u].size();++i){
        int v = M[u][i];
        if(v != fa){
            dfs(v, u);
            if(Q[u].size() < Q[v].size()) swap(Q[u], Q[v]);
            for(auto t : Q[v]){
                if(Q[u].find(t) != Q[u].end()){
                    ans[u] = 1;
                    break;
                }else{
                    Q[u].insert(t);
                }
            }
        }
    }
    if(ans[u] == 1){
        res.push_back(u);
        tot++; Q[u].clear();
    }
}
int main(){
    cin >> n;
    int u, v;
    for(int i=1;i<n;++i){
        scanf("%d %d", &u, &v);
        M[u].push_back(v);
        M[v].push_back(u);
    }
    cin >> m;
    for(int i=0;i<m;++i){
        scanf("%d %d", &u, &v);
        if(u == v){
            ans[u] = 1; continue;
        }
        Q[u].insert(i);
        Q[v].insert(i);
    }
    dfs(1, 0);
    cout << res.size() << endl;
    for(int i = res.size() - 1; i >= 0; i--){
        printf("%d ", res[i]);
    }
    return 0;
}

详细

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

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 27ms
memory: 141944kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 13
17 15
18 16
19 17
20 18
...

output:

2
3 10 

result:

ok ok

Test #2:

score: 0
Accepted
time: 36ms
memory: 141944kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
6 13 

result:

ok ok

Test #3:

score: 0
Accepted
time: 20ms
memory: 141948kb

input:

20
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 8
10 9
11 10
12 6
13 2
14 7
15 14
16 11
17 12
18 17
19 7
20 15
5
4 ...

output:

3
1 4 11 

result:

ok ok

Test #4:

score: 0
Accepted
time: 20ms
memory: 141940kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 28ms
memory: 141944kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 6
10 8
11 10
12 11
13 11
14 12
15 13
16 9
17 15
18 16
19 16
20 17
1...

output:

6
1 3 19 7 10 17 

result:

ok ok

Test #6:

score: 0
Accepted
time: 28ms
memory: 141944kb

input:

20
2 1
3 2
4 3
5 3
6 5
7 4
8 6
9 8
10 7
11 7
12 10
13 12
14 13
15 9
16 14
17 16
18 16
19 17
20 15
12...

output:

3
9 4 13 

result:

ok ok

Test #7:

score: 0
Accepted
time: 24ms
memory: 141940kb

input:

20
2 1
3 1
4 2
5 3
6 4
7 5
8 6
9 7
10 8
11 9
12 10
13 11
14 10
15 14
16 10
17 13
18 4
19 18
20 4
2
1...

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 20ms
memory: 141944kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 4
8 7
9 6
10 9
11 8
12 11
13 10
14 10
15 12
16 14
17 13
18 17
19 14
20 18
4...

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 19ms
memory: 141948kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 8
12 10
13 12
14 8
15 13
16 8
17 8
18 16
19 15
20 11
12
8...

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 20ms
memory: 141940kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 7
10 9
11 10
12 8
13 11
14 12
15 13
16 14
17 15
18 16
19 18
20 19
1...

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 24ms
memory: 142012kb

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:

11
317 585 258 397 53 186 471 235 280 289 131 

result:

ok ok

Test #12:

score: 0
Accepted
time: 20ms
memory: 142016kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 12
16 14
17 16
18 17
19 18
20 1...

output:

16
179 561 114 154 822 418 96 315 526 110 610 109 152 463 285 469 

result:

ok ok

Test #13:

score: 0
Accepted
time: 20ms
memory: 141988kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

2
40 305 

result:

ok ok

Test #14:

score: 0
Accepted
time: 35ms
memory: 142016kb

input:

1000
2 1
3 2
4 3
5 4
6 4
7 5
8 6
9 7
10 8
11 9
12 11
13 10
14 12
15 14
16 13
17 15
18 16
19 17
20 18...

output:

15
77 218 391 738 410 111 277 460 164 36 281 161 236 408 577 

result:

ok ok

Test #15:

score: 0
Accepted
time: 31ms
memory: 142040kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

17
46 104 126 293 460 526 513 230 313 439 546 694 462 469 324 504 646 

result:

ok ok

Test #16:

score: 0
Accepted
time: 36ms
memory: 141984kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

6
18 168 311 114 201 651 

result:

ok ok

Test #17:

score: 0
Accepted
time: 32ms
memory: 142024kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 13
16 14
17 16
18 17
19 15
20 1...

output:

16
11 341 567 249 42 586 171 68 113 373 649 311 423 450 361 497 

result:

ok ok

Test #18:

score: 0
Accepted
time: 28ms
memory: 141988kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 6
9 8
10 9
11 7
12 11
13 10
14 12
15 13
16 15
17 14
18 15
19 18
20 16...

output:

4
15 437 387 167 

result:

ok ok

Test #19:

score: 0
Accepted
time: 31ms
memory: 141992kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

10
210 33 367 236 372 978 364 363 158 873 

result:

ok ok

Test #20:

score: 0
Accepted
time: 32ms
memory: 141984kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 3
9 8
10 9
11 10
12 11
13 7
14 12
15 13
16 7
17 14
18 17
19 15
20 16
...

output:

5
85 118 241 7 307 

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 1072ms
memory: 205284kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 11
15 14
16 13
17 15
18 16
19 17
2...

output:

5
16698 23494 260 10715 49620 

result:

ok ok

Test #22:

score: 0
Accepted
time: 1238ms
memory: 205696kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

45
2404 82029 115253 233457 11999 500929 106037 604192 16080 31547 24573 90763 142420 25801 216079 1...

result:

ok ok

Test #23:

score: 0
Accepted
time: 1324ms
memory: 218448kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

288
553 45282 52305 82088 285917 618513 860545 192200 1097183 497304 911742 276788 898972 179687 322...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1240ms
memory: 211160kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

172
4997 8750 433432 144601 766288 82050 380023 259287 693969 208442 280573 548688 87371 228932 6307...

result:

ok ok

Test #25:

score: 0
Accepted
time: 1931ms
memory: 256156kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

635
969 1796 5534 8367 85692 803946 129631 151043 494392 825309 525383 640853 612210 1122973 318533 ...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1331ms
memory: 205620kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

27
5198 114045 48041 50127 247729 818338 38220 61117 86675 188792 785042 8142 104143 81891 199173 11...

result:

ok ok

Test #27:

score: 0
Accepted
time: 1646ms
memory: 205220kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

6
490 3177 34548 8562 5695 83430 

result:

ok ok

Test #28:

score: 0
Accepted
time: 1319ms
memory: 213152kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

220
1404 41605 54862 153746 319357 550840 358520 611572 506710 129407 942737 748677 262331 191898 45...

result:

ok ok

Test #29:

score: 0
Accepted
time: 1196ms
memory: 205332kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

18
35966 9580 56381 45067 2171 28264 373647 40324 77646 181356 16009 217782 68915 39104 77795 76116 ...

result:

ok ok

Test #30:

score: 0
Accepted
time: 1233ms
memory: 205828kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

45
30601 38898 63158 283753 22786 109850 185280 180100 431102 77846 102267 178850 453569 14598 25916...

result:

ok ok

Test #31:

score: 0
Accepted
time: 1226ms
memory: 205796kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

32
1116 85909 32582 78137 135320 23111 106921 21197 16424 67788 240588 391430 27073 172115 398423 61...

result:

ok ok

Test #32:

score: 0
Accepted
time: 1305ms
memory: 205396kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

5
15117 6708 5384 19941 80900 

result:

ok ok

Test #33:

score: 0
Accepted
time: 1249ms
memory: 205468kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

11
4421 78545 46860 57419 326571 6325 8344 44930 16347 299866 35897 

result:

ok ok

Test #34:

score: 0
Accepted
time: 1213ms
memory: 205224kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

2
5187 7452 

result:

ok ok

Test #35:

score: 0
Accepted
time: 1241ms
memory: 211776kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

192
800 3704 4872 14477 84582 192531 519772 418604 1143239 100042 538758 597503 1527936 183733 62075...

result:

ok ok

Test #36:

score: 0
Accepted
time: 1443ms
memory: 237496kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

489
39 13186 79500 156749 210507 297518 791525 903264 1596990 385789 259752 449597 801012 1485763 86...

result:

ok ok

Test #37:

score: 0
Accepted
time: 1082ms
memory: 205320kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

2
1572 10047 

result:

ok ok

Test #38:

score: 0
Accepted
time: 1132ms
memory: 205532kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

6
5177 16799 17244 342086 21899 124227 

result:

ok ok

Test #39:

score: 0
Accepted
time: 1056ms
memory: 205516kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

3
9574 114239 37101 

result:

ok ok

Test #40:

score: 0
Accepted
time: 1390ms
memory: 232608kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

434
2752 3689 16278 111779 603953 807328 312694 435358 1385278 65194 656635 175863 234746 597155 518...

result:

ok ok

Test #41:

score: 0
Accepted
time: 1445ms
memory: 205336kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

3
4025 12701 18588 

result:

ok ok

Test #42:

score: 0
Accepted
time: 1212ms
memory: 205904kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

46
75176 864760 95276 21454 448384 38220 458857 113172 120509 323223 23231 132186 55565 23273 91413 ...

result:

ok ok

Test #43:

score: 0
Accepted
time: 1137ms
memory: 205608kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

9
12356 19276 16676 29074 45809 30431 71934 7458 48149 

result:

ok ok

Test #44:

score: 0
Accepted
time: 1162ms
memory: 205436kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

21
3775 10517 30025 100130 18085 58317 7530 207708 149176 147513 42583 154795 337494 8870 34965 5968...

result:

ok ok

Test #45:

score: 0
Accepted
time: 2401ms
memory: 300288kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

902
1097 2377 14419 70713 231795 892541 543037 900999 894109 1726698 249558 497526 415401 470510 688...

result:

ok ok

Test #46:

score: 0
Accepted
time: 1071ms
memory: 205320kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

1
8442 

result:

ok ok

Test #47:

score: 0
Accepted
time: 1330ms
memory: 205364kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

9
6422 22535 409005 19409 5252 56798 24115 215617 36225 

result:

ok ok

Test #48:

score: 0
Accepted
time: 1334ms
memory: 205364kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

5
428 7718 16350 48522 7180 

result:

ok ok

Test #49:

score: 0
Accepted
time: 1303ms
memory: 205368kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

2
1290 14389 

result:

ok ok

Test #50:

score: 0
Accepted
time: 1517ms
memory: 246000kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

559
945 1241 5644 14252 48604 106685 435359 507404 947255 351017 1050435 1115577 1343970 202904 3102...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed