UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213518#2769. 覆盖nullptr_qwq10033956ms185280kbC++111.5kb2024-11-12 19:38:412024-11-12 23:12:44

answer

#include<bits/stdc++.h>
using namespace std;typedef long long LL;const int N=2000005;int n,e,q,tot;int qa[N],qb[N],c[N],lca[N],col[N],fa[N],dfn[N],L[N],R[N],dep[N],b[N],toq;int hed[N],ver[N<<1],nxt[N<<1];vector<pair<int,int>>v[N];void add(int x,int y){ver[++e]=y;nxt[e]=hed[x];hed[x]=e;}inline int getf(int x){if(x==fa[x])return x;else return fa[x]=getf(fa[x]);}void tarjan(int x){col[x]=1;dfn[x]=++tot;L[x]=tot;for(int i=hed[x];i;i=nxt[i])if(col[ver[i]]==0){dep[ver[i]]=dep[x]+1;tarjan(ver[i]);fa[ver[i]]=x;}for(auto i:v[x])if(col[i.first]==2)lca[i.second]=getf(i.first);col[x]=2;R[x]=tot;}inline void read(int&x){char c=getchar();x=0;while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();}bool cmp(int x,int y){return dep[lca[x]]>dep[lca[y]];}inline int lowbit(int x){return x&-x;}inline int query(int x){int ret=0;while(x){ret+=b[x];x-=lowbit(x);}if(ret)return 1;else return 0;}inline void Add(int x,int k){while(x<=n){b[x]+=k;x+=lowbit(x);}}void change(int l,int r){Add(l,1);Add(r+1,-1);}int ans[N];int main(){read(n);for(int i=1;i<n;i++){int x,y;read(x),read(y);add(x,y);add(y,x);}read(q);for(int i=1;i<=q;i++){read(qa[i]),read(qb[i]),c[i]=i;if(qa[i]==qb[i])lca[i]=qa[i];else v[qa[i]].push_back(make_pair(qb[i],i)),v[qb[i]].push_back(make_pair(qa[i],i));}for(int i=1;i<=n;i++)fa[i]=i;tarjan(1);sort(c+1,c+1+q,cmp);for(int i=1;i<=q;i++){int x=c[i];if(query(dfn[qa[x]])||query(dfn[qb[x]]))continue;else change(L[lca[x]],R[lca[x]]),ans[++ans[0]]=lca[x];}printf("%d\n",ans[0]);for(int i=1;i<=ans[0];i++)printf("%d ",ans[i]);return 0;}
Source code, Language: C++11

Details

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

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 12ms
memory: 48132kb

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
10 3

result:

ok ok

Test #2:

score: 0
Accepted
time: 12ms
memory: 48128kb

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
13 6

result:

ok ok

Test #3:

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

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
11 4 1

result:

ok ok

Test #4:

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

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
11 5

result:

ok ok

Test #5:

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

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
17 10 19 7 3 1

result:

ok ok

Test #6:

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

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
13 9 4

result:

ok ok

Test #7:

score: 0
Accepted
time: 12ms
memory: 48116kb

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
8 5

result:

ok ok

Test #8:

score: 0
Accepted
time: 17ms
memory: 48128kb

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
10 4

result:

ok ok

Test #9:

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

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
10 8 3

result:

ok ok

Test #10:

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

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
12 7

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 23ms
memory: 48196kb

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
585 397 471 317 258 289 280 235 186 131 53

result:

ok ok

Test #12:

score: 0
Accepted
time: 14ms
memory: 48200kb

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
822 610 469 526 463 418 315 285 561 152 154 114 109 110 179 96

result:

ok ok

Test #13:

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

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
305 40

result:

ok ok

Test #14:

score: 0
Accepted
time: 12ms
memory: 48200kb

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
738 577 460 408 410 391 277 236 218 111 164 281 161 77 36

result:

ok ok

Test #15:

score: 0
Accepted
time: 22ms
memory: 48224kb

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
694 546 439 462 646 513 526 460 504 313 469 293 324 230 126 104 46

result:

ok ok

Test #16:

score: 0
Accepted
time: 12ms
memory: 48180kb

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
651 311 201 168 114 18

result:

ok ok

Test #17:

score: 0
Accepted
time: 12ms
memory: 48200kb

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
649 497 450 586 567 361 341 373 423 311 249 113 171 68 42 11

result:

ok ok

Test #18:

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

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
387 437 167 15

result:

ok ok

Test #19:

score: 0
Accepted
time: 17ms
memory: 48188kb

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
873 978 364 372 363 367 210 236 158 33

result:

ok ok

Test #20:

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

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
241 307 118 85 7

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 1126ms
memory: 135252kb

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
49620 23494 16698 10715 260

result:

ok ok

Test #22:

score: 0
Accepted
time: 1062ms
memory: 135968kb

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
688613 604192 500929 486244 301547 286931 250167 242712 233457 222879 216079 187293 181476 161032...

result:

ok ok

Test #23:

score: 0
Accepted
time: 1102ms
memory: 144444kb

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
1571406 1457593 1524415 1313659 1333082 1300385 1273833 1258416 1314340 1341353 1270263 1216922 ...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1130ms
memory: 140312kb

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
1419731 1551707 1438642 1339581 1467760 1359562 1155466 1184235 1108051 1053411 1004664 1014013 ...

result:

ok ok

Test #25:

score: 0
Accepted
time: 1347ms
memory: 164600kb

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
1682777 1858710 1570253 1814909 1682196 1677833 1589399 1444687 1482729 1672975 1391826 1679443 ...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1050ms
memory: 135932kb

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
785042 818338 555946 485335 302153 247729 199173 172800 188792 166820 135166 114045 119648 104143...

result:

ok ok

Test #27:

score: 0
Accepted
time: 1181ms
memory: 135160kb

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
83430 34548 8562 5695 3177 490

result:

ok ok

Test #28:

score: 0
Accepted
time: 1097ms
memory: 141312kb

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
1936525 1478908 1340502 1404538 1228505 1205098 1299124 1248765 1148995 1196581 1104581 1027247 ...

result:

ok ok

Test #29:

score: 0
Accepted
time: 1027ms
memory: 135556kb

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
373647 217782 181356 77646 77795 76116 68915 56381 52501 45067 40324 39104 35966 28264 14974 1600...

result:

ok ok

Test #30:

score: 0
Accepted
time: 1079ms
memory: 136300kb

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
909582 611688 581336 525980 453569 431102 337775 283753 274881 287387 217236 180100 177752 178850...

result:

ok ok

Test #31:

score: 0
Accepted
time: 1077ms
memory: 136136kb

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
1248806 406005 398423 391430 395244 240588 172115 157325 156949 135320 112588 106921 85909 78137 ...

result:

ok ok

Test #32:

score: 0
Accepted
time: 1021ms
memory: 135384kb

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
80900 19941 15117 6708 5384

result:

ok ok

Test #33:

score: 0
Accepted
time: 1021ms
memory: 135504kb

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
299866 326571 78545 57419 46860 44930 35897 16347 8344 6325 4421

result:

ok ok

Test #34:

score: 0
Accepted
time: 1031ms
memory: 135040kb

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
7452 5187

result:

ok ok

Test #35:

score: 0
Accepted
time: 1263ms
memory: 140676kb

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
1715717 1582676 1395995 1527936 1371479 1607271 1143239 1252109 1239172 1300716 1129856 1138946 ...

result:

ok ok

Test #36:

score: 0
Accepted
time: 1197ms
memory: 155028kb

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
1824291 1800410 1684630 1724011 1591199 1679195 1583116 1596990 1463769 1655461 1587897 1486485 ...

result:

ok ok

Test #37:

score: 0
Accepted
time: 999ms
memory: 135176kb

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
10047 1572

result:

ok ok

Test #38:

score: 0
Accepted
time: 1016ms
memory: 135560kb

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
342086 124227 21899 17244 16799 5177

result:

ok ok

Test #39:

score: 0
Accepted
time: 1019ms
memory: 135464kb

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
114239 37101 9574

result:

ok ok

Test #40:

score: 0
Accepted
time: 1158ms
memory: 152184kb

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
1690771 1479072 1829375 1644962 1676071 1639745 1617188 1752159 1716509 1521055 1455261 1495757 ...

result:

ok ok

Test #41:

score: 0
Accepted
time: 1029ms
memory: 135208kb

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
18588 12701 4025

result:

ok ok

Test #42:

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

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
1748152 864760 458857 397173 448384 391289 345372 307574 323223 292309 241086 247470 222153 21689...

result:

ok ok

Test #43:

score: 0
Accepted
time: 1002ms
memory: 135676kb

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
71934 48149 45809 30431 29074 19276 16676 12356 7458

result:

ok ok

Test #44:

score: 0
Accepted
time: 1183ms
memory: 135688kb

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
596841 320093 337494 304055 207708 149176 147513 154795 100130 71429 59568 58508 58317 42583 3496...

result:

ok ok

Test #45:

score: 0
Accepted
time: 1723ms
memory: 185280kb

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
1824571 1830969 1857074 1685610 1699068 1946442 1641365 1807564 1698468 1747285 1633540 1719272 ...

result:

ok ok

Test #46:

score: 0
Accepted
time: 996ms
memory: 135188kb

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: 961ms
memory: 135436kb

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
409005 215617 56798 36225 24115 22535 19409 6422 5252

result:

ok ok

Test #48:

score: 0
Accepted
time: 1169ms
memory: 135328kb

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
48522 16350 7718 7180 428

result:

ok ok

Test #49:

score: 0
Accepted
time: 1017ms
memory: 135196kb

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
14389 1290

result:

ok ok

Test #50:

score: 0
Accepted
time: 1459ms
memory: 159516kb

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
1834153 1748863 1758508 1624340 1555404 1497367 1475343 1644842 1582585 1474740 1556611 1779947 ...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-02-28 06:26:28 | 开源项目