ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213571 | #2769. 覆盖 | KXG | 97 | 76467ms | 242916kb | C++11 | 2.8kb | 2024-11-12 20:58:44 | 2024-11-12 23:41:50 |
answer
#include <cstdio>
#include <vector>
using namespace std;
struct BIT {
int n, t[2000010];
void modify(int k, int x) {
for (int i = k; i <= n; i += i & (-i)) {
t[i] += x;
}
}
int query(int k) {
int ans = 0;
for (int i = k; i >= 1; i -= i & (-i)) {
ans += t[i];
}
return ans;
}
} bt;
struct UnionSet {
int n, fa[2000010];
void init() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[find(x)] = find(y);
}
} lcaset;
vector<int> ans;
int n, m, x, y, u, v, X[2000010], Y[2000010], lca[2000010], vis[2000010];
vector<int> G[2000010];
vector<pair<int, int> > queries[2000010];
void tarjan(int u) {
vis[u]++;
for (int i = 0; i < G[u].size(); i++) {
if (!vis[G[u][i]]) {
tarjan(G[u][i]);
lcaset.fa[G[u][i]] = u;
}
}
for (int i = 0; i < queries[u].size(); i++) {
int v = queries[u][i].first, id = queries[u][i].second;
if (vis[v] == 2 && !lca[id]) {
lca[id] = lcaset.find(v);
}
}
vis[u]++;
}
int d[2000010], dfn[2000010], dfe[2000010], times;
void dfs(int u, int f = 0) {
dfn[u] = ++times;
for (int v : G[u]) {
if (v == f) continue;
dfs(v, u);
}
dfe[u] = times;
}
void dfsxy(int u, int f = 0) {
for (int v : G[u]) {
if (v == f) continue;
dfsxy(v, u);
}
for (int i = 0; i < queries[u].size(); i++) {
int now = bt.query(dfn[queries[u][i].first]) + bt.query(dfn[queries[u][i].second]);
if (now == 0) {
ans.push_back(u);
bt.modify(dfn[u], 1);
bt.modify(dfe[u] + 1, -1);
break;
}
}
}
int main() {
scanf("%d", &n);
lcaset.n = n;
bt.n = n;
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
lcaset.init();
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &X[i], &Y[i]);
if (X[i] == Y[i]) lca[i] = X[i];
else {
queries[X[i]].push_back({Y[i], i});
queries[Y[i]].push_back({X[i], i});
}
}
tarjan(1);
for (int i = 1; i <= n; i++) {
queries[i].clear();
}
for (int i = 1; i <= m; i++) {
// printf("lca of %d and %d is %d\n", X[i], Y[i], lca[i]);
queries[lca[i]].push_back({X[i], Y[i]});
}
dfsxy(1);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%d ", ans[i]);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 23ms
memory: 94868kb
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: 94872kb
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: 24ms
memory: 94872kb
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: 23ms
memory: 94868kb
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: 20ms
memory: 94872kb
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 7 19 3 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 24ms
memory: 94872kb
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 4 9
result:
ok ok
Test #7:
score: 0
Accepted
time: 12ms
memory: 94872kb
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: 24ms
memory: 94868kb
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: 20ms
memory: 94872kb
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: 23ms
memory: 94868kb
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: 16ms
memory: 94948kb
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 131 289 280 235 471 186 53 397 258 585 317
result:
ok ok
Test #12:
score: 0
Accepted
time: 20ms
memory: 94948kb
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 469 285 463 152 109 610 110 526 315 96 418 822 154 114 561 179
result:
ok ok
Test #13:
score: 0
Accepted
time: 27ms
memory: 94936kb
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: 40ms
memory: 94944kb
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 577 408 236 161 281 36 164 460 277 111 410 738 391 218 77
result:
ok ok
Test #15:
score: 0
Accepted
time: 29ms
memory: 94960kb
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 646 504 324 469 462 694 546 439 313 230 513 526 460 293 126 104 46
result:
ok ok
Test #16:
score: 0
Accepted
time: 28ms
memory: 94928kb
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 201 114 311 168 18
result:
ok ok
Test #17:
score: 0
Accepted
time: 35ms
memory: 94948kb
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 497 361 450 423 311 649 373 113 68 171 586 42 249 567 341 11
result:
ok ok
Test #18:
score: 0
Accepted
time: 8ms
memory: 94932kb
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 167 387 437 15
result:
ok ok
Test #19:
score: 0
Accepted
time: 15ms
memory: 94936kb
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 158 363 364 978 372 236 367 33 210
result:
ok ok
Test #20:
score: 0
Accepted
time: 8ms
memory: 94932kb
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 307 7 241 118 85
result:
ok ok
Subtask #3:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 2376ms
memory: 189804kb
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 10715 260 23494 16698
result:
ok ok
Test #22:
score: 0
Accepted
time: 2397ms
memory: 190500kb
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 11229 7524 58888 181476 187293 688613 250167 98852 37754 242712 222879 91612 486244 286931 164683...
result:
ok ok
Test #23:
score: 0
Accepted
time: 3059ms
memory: 199148kb
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 337025 168778 522156 341203 577622 308988 97622 194033 1341353 370758 787195 433073 834931 49484...
result:
ok ok
Test #24:
score: 0
Accepted
time: 2556ms
memory: 194840kb
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 1014013 529921 694297 520180 599257 631816 181786 129828 470110 445132 69263 79221 260919 141973...
result:
ok ok
Test #25:
score: 0
Accepted
time: 2704ms
memory: 220540kb
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 632643 1062517 615615 1321467 974900 624121 1147835 604799 554132 676563 943663 420074 254648 44...
result:
ok ok
Test #26:
score: 0
Accepted
time: 2374ms
memory: 190424kb
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 71286 172800 135166 27608 485335 7509 555946 56909 166820 34761 302153 119648 199173 81891 104143...
result:
ok ok
Test #27:
score: 0
Accepted
time: 2305ms
memory: 189728kb
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 5695 8562 34548 3177 490
result:
ok ok
Test #28:
score: 0
Accepted
time: 3051ms
memory: 195976kb
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 305408 533550 282162 1340502 836376 1936525 761348 332688 909621 948215 251198 326676 68125 8624...
result:
ok ok
Test #29:
score: 0
Accepted
time: 2238ms
memory: 190032kb
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 52501 14974 76116 77795 39104 68915 217782 16009 181356 77646 40324 373647 28264 2171 45067 56381...
result:
ok ok
Test #30:
score: 0
Accepted
time: 2601ms
memory: 190800kb
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 581336 45646 525980 126715 611688 71846 40197 108135 217236 12786 61559 22736 135687 26716 172073...
result:
ok ok
Test #31:
score: 0
Accepted
time: 2441ms
memory: 190656kb
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 157325 1248806 49460 54106 27779 395244 156949 60225 79924 406005 112588 23813 63492 49619 60014 ...
result:
ok ok
Test #32:
score: 0
Accepted
time: 2414ms
memory: 189900kb
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 5384 6708 15117
result:
ok ok
Test #33:
score: 0
Accepted
time: 2281ms
memory: 190100kb
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 35897 299866 16347 44930 8344 6325 326571 57419 46860 78545 4421
result:
ok ok
Test #34:
score: 0
Accepted
time: 2368ms
memory: 189648kb
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: 2401ms
memory: 195204kb
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 798022 683274 189151 272780 395686 178707 167947 288168 84233 42016 213201 246297 65882 401226 3...
result:
ok ok
Test #36:
score: 0
Accepted
time: 2552ms
memory: 210460kb
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 1290894 773197 168673 549010 1110040 463781 101013 564050 878684 504977 144833 550142 490628 583...
result:
ok ok
Test #37:
score: 0
Accepted
time: 2294ms
memory: 189796kb
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: 2252ms
memory: 190096kb
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 124227 21899 342086 17244 16799 5177
result:
ok ok
Test #39:
score: 0
Accepted
time: 2321ms
memory: 189964kb
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 37101 114239 9574
result:
ok ok
Test #40:
score: 0
Accepted
time: 2566ms
memory: 207132kb
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 231435 1065369 1047494 1043183 862445 364587 150861 935117 12689 107063 890252 1119825 316606 21...
result:
ok ok
Test #41:
score: 0
Accepted
time: 2283ms
memory: 189796kb
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: 2580ms
memory: 190656kb
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 345372 63057 30104 12634 247470 129242 189949 23016 135187 397173 307574 181178 172800 241086 788...
result:
ok ok
Test #43:
score: 0
Accepted
time: 2303ms
memory: 190216kb
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 48149 7458 71934 30431 45809 29074 16676 19276 12356
result:
ok ok
Test #44:
score: 0
Accepted
time: 2421ms
memory: 190188kb
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 59568 320093 304055 58508 71429 596841 34965 8870 337494 154795 42583 147513 149176 207708 7530 5...
result:
ok ok
Test #45:
score: 0
Accepted
time: 3703ms
memory: 242916kb
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 707120 510765 1126170 709056 682262 589612 1719028 553741 936823 544626 254140 219178 728374 700...
result:
ok ok
Test #46:
score: 0
Accepted
time: 2795ms
memory: 189696kb
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: 2264ms
memory: 189944kb
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 36225 215617 24115 56798 5252 19409 409005 22535 6422
result:
ok ok
Test #48:
score: 0
Accepted
time: 2258ms
memory: 189896kb
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 7180 48522 16350 7718 428
result:
ok ok
Test #49:
score: 0
Accepted
time: 2953ms
memory: 189796kb
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: 2925ms
memory: 215160kb
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 306701 797261 566812 1241533 639642 297503 69301 329799 833615 498524 32866 199612 441612 303641...
result:
ok ok
Extra Test:
score: -3
Extra Test Failed : Time Limit Exceeded on 5
input:
2000000 2 1 3 1 4 3 5 2 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 4 18 17 19 18 20...
output:
840 518497 969943 1470013 1122548 659089 957494 1393045 657724 370789 301952 1495924 619037 950819 5...