ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213523 | #2769. 覆盖 | nodgd | 100 | 31378ms | 257624kb | C++11 | 2.2kb | 2024-11-12 19:47:31 | 2024-11-12 23:20:03 |
answer
#include <bits/stdc++.h>
using namespace std;
namespace FastRead{
char buf[1000005], *s = buf, *t = buf, ch, f;
#define gc() s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++
template <typename T>
inline void Read(T &x)
{
x = f = 0, ch = gc();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = 1;
ch = gc();
}
while('0' <= ch && ch <= '9') x = x * 10 + ch - 48, ch = gc();
f && (x = -x);
}
};
using FastRead::Read;
const int N = 2e6 + 5, K = 22;
int n, m;
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N][K], dep[N], in[N], out[N], dfst;
struct Node{
int u, v, w, d;
bool operator <(const Node &w) const
{
return d > w.d;
}
}x[N];
int cnt, vis[N], c[N];
inline void Add(int a, int b)
{
ne[ ++ idx] = la[a];
la[a] = idx;
en[idx] = b;
}
inline void DFS(int u, int f)
{
fa[u][0] = f, dep[u] = dep[f] + 1;
for(int i = 1; i < K; i ++ ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
in[u] = ++ dfst;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(v != f) DFS(v, u);
}
out[u] = dfst;
}
inline int LCA(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(int i = K - 1; i >= 0; i -- )
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = K - 1; i >= 0; i -- )
if(fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
inline void Modify(int i, int d)
{
for(; i <= n; i += i & -i) c[i] += d;
}
inline int Sum(int i)
{
int s = 0;
for(; i; i &= i - 1) s += c[i];
return s;
}
int main()
{
Read(n);
for(int i = 1; i < n; i ++ )
{
int a, b;
Read(a), Read(b);
Add(a, b), Add(b, a);
}
DFS(1, 0);
Read(m);
for(int i = 1; i <= m; i ++ )
{
Read(x[i].u), Read(x[i].v);
x[i].w = LCA(x[i].u, x[i].v);
x[i].d = dep[x[i].w];
}
sort(x + 1, x + m + 1);
for(int i = 1; i <= m; i ++ )
{
// printf("*%d %d %d\n", x[i].u, x[i].v, x[i].w);
if(Sum(in[x[i].u]) + Sum(in[x[i].v]) - Sum(in[x[i].w]) - Sum(in[fa[x[i].w][0]]) == 0)
{
vis[x[i].w] = 1;
cnt ++ ;
Modify(in[x[i].w], 1);
Modify(out[x[i].w] + 1, -1);
}
}
printf("%d\n", cnt);
for(int i = 1; i <= n; i ++ ) if(vis[i]) printf("%d ", i);
puts("");
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 1208kb
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: 0ms
memory: 1204kb
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: 0ms
memory: 1204kb
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: 0ms
memory: 1204kb
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: 0ms
memory: 1208kb
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 7 10 17 19
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 1208kb
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 4 9 13
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 1192kb
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: 0ms
memory: 1208kb
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: 0ms
memory: 1208kb
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: 0ms
memory: 1204kb
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: 0ms
memory: 1336kb
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 53 131 186 235 258 280 289 317 397 471 585
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 1340kb
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 96 109 110 114 152 154 179 285 315 418 463 469 526 561 610 822
result:
ok ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 1336kb
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: 0ms
memory: 1340kb
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 36 77 111 161 164 218 236 277 281 391 408 410 460 577 738
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 1344kb
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 230 293 313 324 439 460 462 469 504 513 526 546 646 694
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 1332kb
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 114 168 201 311 651
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 1340kb
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 42 68 113 171 249 311 341 361 373 423 450 497 567 586 649
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 1332kb
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 167 387 437
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 1336kb
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 33 158 210 236 363 364 367 372 873 978
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 1332kb
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 7 85 118 241 307
result:
ok ok
Subtask #3:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 849ms
memory: 237012kb
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 260 10715 16698 23494 49620
result:
ok ok
Test #22:
score: 0
Accepted
time: 950ms
memory: 238048kb
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 7524 11229 11999 14383 16080 18852 24573 25801 31547 35420 37754 42334 58888 69242 72415 820...
result:
ok ok
Test #23:
score: 0
Accepted
time: 1013ms
memory: 243352kb
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 5636 9673 9795 15417 22482 28415 29113 30841 31695 36154 36370 41110 45282 46034 47993 48884...
result:
ok ok
Test #24:
score: 0
Accepted
time: 1187ms
memory: 241120kb
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 17928 18489 27327 30718 32013 33965 34115 42664 44246 55789 56336 56495 57194 69263 74...
result:
ok ok
Test #25:
score: 0
Accepted
time: 1625ms
memory: 250712kb
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 7302 8367 9149 10058 10082 10729 13481 14831 15038 17852 18658 20221 22753 25477 2...
result:
ok ok
Test #26:
score: 0
Accepted
time: 1043ms
memory: 237768kb
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 7509 8142 27608 34761 38220 48041 50127 56909 61117 71286 81891 86675 104143 114045 119648 1...
result:
ok ok
Test #27:
score: 0
Accepted
time: 835ms
memory: 237012kb
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 5695 8562 34548 83430
result:
ok ok
Test #28:
score: 0
Accepted
time: 1024ms
memory: 241908kb
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 2780 5137 10384 13852 18479 22969 35367 37404 38380 41605 44793 46628 49267 50316 54862 579...
result:
ok ok
Test #29:
score: 0
Accepted
time: 857ms
memory: 237448kb
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 2171 9580 14974 16009 28264 35966 39104 40324 45067 52501 56381 68915 76116 77646 77795 181356 21...
result:
ok ok
Test #30:
score: 0
Accepted
time: 949ms
memory: 238148kb
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 2737 4251 12786 13429 14598 22080 22736 22786 25916 26716 30601 38898 40197 45646 47158 61559 631...
result:
ok ok
Test #31:
score: 0
Accepted
time: 1125ms
memory: 237864kb
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 16424 21197 23111 23813 27073 27779 32582 47061 49460 49619 54106 60014 60225 61690 63492 67...
result:
ok ok
Test #32:
score: 0
Accepted
time: 1140ms
memory: 237088kb
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 5384 6708 15117 19941 80900
result:
ok ok
Test #33:
score: 0
Accepted
time: 828ms
memory: 237204kb
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 6325 8344 16347 35897 44930 46860 57419 78545 299866 326571
result:
ok ok
Test #34:
score: 0
Accepted
time: 856ms
memory: 236864kb
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: 933ms
memory: 241512kb
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 12578 14477 19995 22579 25124 29417 31207 32243 34402 42016 44099 44679 45783 4791...
result:
ok ok
Test #36:
score: 0
Accepted
time: 1343ms
memory: 247396kb
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 5656 7050 7487 10829 12376 13186 13483 24437 27366 29300 31447 37089 37325 41271 41767 45145 ...
result:
ok ok
Test #37:
score: 0
Accepted
time: 857ms
memory: 236896kb
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: 853ms
memory: 237136kb
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 21899 124227 342086
result:
ok ok
Test #39:
score: 0
Accepted
time: 826ms
memory: 237052kb
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 37101 114239
result:
ok ok
Test #40:
score: 0
Accepted
time: 1184ms
memory: 246340kb
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 3375 3689 4991 6053 9618 12539 12689 13788 16278 19244 20277 22749 25323 28033 30314 36310 ...
result:
ok ok
Test #41:
score: 0
Accepted
time: 856ms
memory: 236956kb
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: 984ms
memory: 238168kb
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 1396 4100 10862 12634 18427 21454 23016 23231 23273 30104 38220 53924 55565 63057 75176 78809 795...
result:
ok ok
Test #43:
score: 0
Accepted
time: 835ms
memory: 237228kb
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 7458 12356 16676 19276 29074 30431 45809 48149 71934
result:
ok ok
Test #44:
score: 0
Accepted
time: 873ms
memory: 237540kb
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 7530 8870 10517 18085 30025 34965 42583 58317 58508 59568 71429 100130 147513 149176 154795 ...
result:
ok ok
Test #45:
score: 0
Accepted
time: 2220ms
memory: 257624kb
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 2384 2850 4587 8343 10511 12075 12386 12906 14030 14419 14466 16460 17707 21340 21375 ...
result:
ok ok
Test #46:
score: 0
Accepted
time: 850ms
memory: 236872kb
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: 839ms
memory: 237168kb
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 5252 6422 19409 22535 24115 36225 56798 215617 409005
result:
ok ok
Test #48:
score: 0
Accepted
time: 852ms
memory: 237004kb
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 7180 7718 16350 48522
result:
ok ok
Test #49:
score: 0
Accepted
time: 1230ms
memory: 236892kb
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: 1561ms
memory: 248964kb
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 8082 9005 9959 10848 12448 12793 14252 20587 20906 23833 27004 27886 28406 29166 3...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed