UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213550#2769. 覆盖KXG6042927ms362828kbC++112.2kb2024-11-12 20:36:262024-11-12 23:34:34

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;
vector<int> ans;
int n, m, x, y, u, v;
vector<int> G[2000010];
vector<pair<int, int> > queries[2000010];
int fa[22][2000010], d[2000010], dfn[2000010], dfe[2000010], times;
void dfs(int u, int f = 0) {
    dfn[u] = ++times;
    fa[0][u] = f;
    d[u] = d[f] + 1;
    for (int v : G[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
    dfe[u] = times;
}
void init() {
    for (int i = 1; i < 22; i++) {
        for (int j = 1; j <= n; j++) {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = 21; i >= 0; i--) {
        if (d[fa[i][y]] >= d[x]) {
            y = fa[i][y];
        }
    }
    if (x == y) return x;
    for (int i = 21; i >= 0; i--) {
        if (fa[i][x] != fa[i][y]) {
            x = fa[i][x];
            y = fa[i][y];
        }
    }
    return fa[0][x];
}
void dfsxy(int u) {
    for (int v : G[u]) {
        if (v == fa[0][u]) continue;
        dfsxy(v);
    }
    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);
    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);
    init();
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        queries[lca(x, y)].push_back({x, y});
    }
    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: 27ms
memory: 94944kb

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: 15ms
memory: 94940kb

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: 8ms
memory: 94948kb

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: 19ms
memory: 94940kb

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: 24ms
memory: 94948kb

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: 16ms
memory: 94948kb

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: 20ms
memory: 94944kb

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

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: 94944kb

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: 8ms
memory: 94944kb

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: 95080kb

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: 11ms
memory: 95076kb

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: 16ms
memory: 95068kb

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: 37ms
memory: 97124kb

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: 12ms
memory: 95096kb

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: 17ms
memory: 95068kb

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

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: 17ms
memory: 95072kb

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: 12ms
memory: 95080kb

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: 4ms
memory: 95068kb

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: 0
Time Limit Exceeded

Test #21:

score: 40
Accepted
time: 1668ms
memory: 353368kb

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: 1639ms
memory: 354212kb

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: 1893ms
memory: 358256kb

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: 1737ms
memory: 356804kb

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: 3347ms
memory: 362828kb

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: 1566ms
memory: 353952kb

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: 1547ms
memory: 353300kb

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: 2011ms
memory: 357240kb

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: 1558ms
memory: 353632kb

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: 1651ms
memory: 354420kb

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: 1534ms
memory: 354120kb

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: 1724ms
memory: 353388kb

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: 1542ms
memory: 353596kb

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: 1527ms
memory: 353216kb

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: 1819ms
memory: 356916kb

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: 2452ms
memory: 360848kb

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: 1564ms
memory: 353288kb

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: 1630ms
memory: 353508kb

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: 1554ms
memory: 353388kb

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: 2307ms
memory: 359896kb

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: 1556ms
memory: 353320kb

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: 1571ms
memory: 354288kb

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: 1628ms
memory: 353616kb

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: 1589ms
memory: 353772kb

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: -40
Time Limit Exceeded

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:


result: