QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127803#5020. 举办乘凉州喵,举办乘凉州谢谢喵pandapythoner7 388ms101328kbC++208.4kb2023-07-20 05:58:032023-07-20 05:58:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 05:58:05]
  • 评测
  • 测评结果:7
  • 用时:388ms
  • 内存:101328kb
  • [2023-07-20 05:58:03]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

struct Fenwick {
    int n;
    vector<int> t;

    void build(int _n) {
        n = _n;
        t.assign(n + 1, 0);
    }

    void add(int i) {
        i += 1;
        if (i <= 0 || i > n) {
            assert(0);
        }
        while (i <= n) {
            t[i] += 1;
            i = (i | (i - 1)) + 1;
        }
    }

    int get(int r) {
        r += 1;
        if (r <= 0) {
            return 0;
        }
        r = min(r, n);
        int rs = 0;
        while (r > 0) {
            rs += t[r];
            r = (r & (r - 1));
        }
        return rs;
    }
};

struct ask {
    int u, v;
    int d;
};

struct bbr {
    int d, f, i;
};

int n, q;
vector<vector<int>> g;
vector<ask> asks;
vector<int> sz;
vector<int> vmp;
vector<int> pr, ppr;
vector<int> dpth, dstx, dsty;
vector<vector<bbr>> b1, b2, b3, b4;
Fenwick f1, f2, f3;
vector<int> rs;

void dfs1(int v, int p) {
    sz[v] = 1;
    int mx_sz_i = -1;
    int mx_sz = -1;
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (to == p) {
            continue;
        }
        dfs1(to, v);
        sz[v] += sz[to];
        if (sz[to] > mx_sz) {
            mx_sz = sz[to];
            mx_sz_i = i;
        }
    }
    if (mx_sz_i != -1) {
        swap(g[v][0], g[v][mx_sz_i]);
    }
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (to == p) {
            g[v].erase(g[v].begin() + i);
            break;
        }
    }
}

void dfs2(int v, int &c) {
    vmp[v] = c;
    c++;
    for (auto to : g[v]) {
        dfs2(to, c);
    }
}

void hld_reorder() {
    sz.resize(n);
    dfs1(0, -1);
    vmp.resize(n);
    int c = 0;
    dfs2(0, c);
    vector<vector<int>> ng(n, vector<int>());
    for (int v = 0; v < n; v += 1) {
        for (auto to : g[v]) {
            ng[vmp[v]].push_back(vmp[to]);
        }
    }
    g.swap(ng);
    for (auto &a : asks) {
        a.u = vmp[a.u];
        a.v = vmp[a.v];
    }
}

void dfs3(int v, int p, int pp, int h, int y) {
    dpth[v] = h;
    pr[v] = p;
    ppr[v] = pp;
    dsty[v] = y;
    dstx[v] = 0;
    sz[v] = 1;
    for (int i = 0; i < (int)g[v].size(); i += 1) {
        int to = g[v][i];
        if (i == 0) {
            dfs3(to, v, pp, h + 1, y + 1);
            dstx[v] = dstx[to] + 1;
        } else {
            dfs3(to, v, to, h + 1, 0);
        }
        sz[v] += sz[to];
    }
}

void build() {
    hld_reorder();
    sz.resize(n);
    pr.resize(n);
    ppr.resize(n);
    dpth.resize(n);
    dstx.resize(n);
    dsty.resize(n);
    dfs3(0, -1, 0, 0, 0);
}

void dfs4(int v, int bnd, int h, int x) {
    f1.add(h);
    f2.add(h + x);
    for (auto to : g[v]) {
        if (to == bnd) {
            continue;
        }
        dfs4(to, bnd, h + 1, x);
    }
}

void dfs5(int v, int bnd, int h, int x) {
    f3.add(h + x);
    for (auto to : g[v]) {
        if (to == bnd) {
            continue;
        }
        dfs4(to, bnd, h + 1, x);
    }
}

void solve_rec(int v) {
    f1.build(sz[v]);
    f2.build(sz[v]);
    f3.build(sz[v]);
    vector<int> way;
    int u = v;
    while (1) {
        way.push_back(u);
        int bnd = -1;
        if (!g[u].empty()) {
            bnd = g[u][0];
        }
        dfs4(u, bnd, 0, dstx[u]);
        for (auto [d, f, i] : b1[u]) {
            rs[i] += f * f1.get(d);
        }
        for (auto [d, f, i] : b2[u]) {
            rs[i] += f * f2.get(d);
        }
        if (g[u].empty()) {
            break;
        }
        u = g[u][0];
    }
    reverse(all(way));
    for (auto u : way) {
        int bnd = -1;
        if (!g[u].empty()) {
            bnd = g[u][0];
        }
        dfs5(u, bnd, 0, dsty[u]);
        for (auto [d, f, i] : b3[u]) {
            rs[i] += f * f3.get(d);
        }
    }
    for (auto [d, f, i] : b4[v]) {
        rs[i] += f * f3.get(d);
    }
    u = v;
    while (1) {
        for (int i = 1; i < (int)g[u].size(); i += 1) {
            solve_rec(g[u][i]);
        }
        if (g[u].empty()) {
            break;
        }
        u = g[u][0];
    }
    // g[n + 1].push_back(0);
}

void solve() {
    rs.assign(q, 0);
    build();
    b1.assign(n, {});
    b2.assign(n, {});
    b3.assign(n, {});
    b4.assign(n, {});
    for (int i = 0; i < q; i += 1) {
        auto a = asks[i];
        auto [u, v, d] = a;
        while (ppr[u] != ppr[v]) {
            if (dpth[ppr[u]] > dpth[ppr[v]]) {
                b1[u].push_back(bbr{d, 1, i});
                if (!g[u].empty()) {
                    b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
                }
                b4[ppr[u]].push_back(bbr{d - 1, -1, i});
                u = pr[ppr[u]];
            } else {
                b1[v].push_back(bbr{d, 1, i});
                if (!g[v].empty()) {
                    b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
                }
                b4[ppr[v]].push_back(bbr{d - 1, -1, i});
                v = pr[ppr[v]];
            }
        }
        if (dpth[u] > dpth[v]) {
            b1[u].push_back(bbr{d, 1, i});
            if (!g[u].empty()) {
                b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
            }
            if (v != ppr[v]) {
                b1[pr[v]].push_back(bbr{d, -1, i});
            }
            u = v;
        } else {
            b1[v].push_back(bbr{d, 1, i});
            if (!g[v].empty()) {
                b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
            }
            if (u != ppr[u]) {
                b1[pr[u]].push_back(bbr{d, -1, i});
            }
            v = u;
        }
        int dst = 1;
        v = pr[v];
        while (v != -1) {
            if (dst > d) {
                break;
            }
            b2[v].push_back(bbr{d + dstx[v] - dst, 1, i});
            dst += (v - ppr[v] + 1);
            b4[ppr[u]].push_back(bbr{d - dst - 1, -1, i});
            v = pr[ppr[v]];
        }
    }
    solve_rec(0);
}

void dfs_bebra(int v, int p, int h, vector<int> &d) {
    d[v] = h;
    for (auto to : g[v]) {
        if (to == p) {
            continue;
        }
        dfs_bebra(to, v, h + 1, d);
    }
}

void solve_slow() {
    hld_reorder();
    for (int v = n - 1; v >= 0; v -= 1) {
        for (auto to : g[v]) {
            g[to].push_back(v);
        }
    }
    rs.assign(q, 0);
    vector<vector<int>> dsts(n, vector<int>(n));
    for (int i = 0; i < n; i += 1) {
        dfs_bebra(i, -1, 0, dsts[i]);
    }
    for (int i = 0; i < q; i += 1) {
        auto [u, v, d] = asks[i];
        for (int j = 0; j < n; j += 1) {
            int dst = (dsts[u][j] + dsts[v][j] - dsts[u][v]) / 2;
            if (dst <= d) {
                rs[i] += 1;
            }
        }
    }
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        n = rnd() % 20 + 1;
        vector<vector<int>> mg(n);
        for (int v = 1; v < n; v += 1) {
            int u = rnd() % v;
            mg[u].push_back(v);
            mg[v].push_back(u);
        }
        q = rnd() % 20 + 1;
        vector<ask> masks(q);
        for (int i = 0; i < q; i += 1) {
            int u = rnd() % n;
            int v = rnd() % n;
            int d = rnd() % n;
            masks[i] = ask{u, v, d};
        }
        g = mg;
        asks = masks;
        solve();
    }
}

int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    g.assign(n, vector<int>());
    for (int i = 0; i < n - 1; i += 1) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> q;
    asks.resize(q);
    for (int i = 0; i < q; i += 1) {
        int u, v, d;
        cin >> u >> v >> d;
        --u;
        --v;
        asks[i] = ask{u, v, d};
    }
    solve_slow();
    for (int i = 0; i < q; i += 1) {
        cout << rs[i] << "\n";
    }
    return 0;
}

/*
6
1 2
2 3
2 4
1 5
4 6
1
3 3 2


*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 366ms
memory: 101016kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

3226
2028
4988
208
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
49...

result:

ok 4966 numbers

Test #2:

score: 0
Accepted
time: 154ms
memory: 98156kb

input:

4914
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27 ...

output:

3378
4914
231
4914
4914
3378
22
4914
4914
2559
4914
75
219
1407
1138
863
24
3890
4914
4914
399
399
13
139
77
4914
4095
3071
4914
23
151
110
1407
43
54
4914
4914
1919
2559
77
735
3071
24
133
479
4914
33
831
4
4914
4914
79
4914
199
3890
3071
73
567
15
75
21
126
4914
4914
203
4914
75
127
62
41
4914
409...

result:

ok 4975 numbers

Test #3:

score: 0
Accepted
time: 325ms
memory: 98340kb

input:

4921
1151 2767
2767 322
322 4451
4451 4867
4867 1265
1265 3197
3197 3890
3890 1052
1052 1407
1407 1578
1578 566
566 2965
2965 260
260 4908
4908 308
308 553
553 2845
2845 4249
4249 1284
1284 73
73 1088
1088 277
277 1878
1878 4128
4128 3609
3609 2126
2126 149
149 3467
3467 1653
1653 4913
4913 3604
360...

output:

4921
3192
3260
3983
949
2080
605
3471
4901
2020
2552
1570
3325
3643
458
1296
3072
3423
3045
2569
1720
3195
1908
4397
1536
2799
3072
2443
3176
3311
1403
1119
842
3028
2387
1903
2303
4921
2149
1974
4153
2053
2888
2344
3264
3709
3443
3601
2571
1207
4519
3745
959
1920
1305
1706
1743
522
1266
2153
1812
1...

result:

ok 4930 numbers

Test #4:

score: 0
Accepted
time: 282ms
memory: 99392kb

input:

4942
877 4180
4180 4409
4409 2233
2233 3491
3491 3459
3459 4501
4501 2192
2192 3539
3539 4379
4379 4346
4346 1553
1553 2100
2100 3426
3426 3461
3461 811
811 2981
2981 1493
1493 610
610 599
599 1741
1741 3216
3216 1646
1646 1016
1016 3757
3757 2570
2570 2900
2900 4649
4649 1014
1014 538
538 4288
4288...

output:

4236
3338
4942
4942
4942
4942
1551
1272
3885
4140
4942
3627
3132
3991
3157
4024
4942
4942
3761
3064
238
4942
4942
4942
4942
4942
2256
4942
649
4496
4942
4942
4491
866
4208
4942
4942
4726
4942
4462
4942
4942
4234
2676
2593
4942
4088
4942
2704
3344
3560
4942
4942
4461
4511
4634
3437
2884
3842
4942
494...

result:

ok 4910 numbers

Test #5:

score: 0
Accepted
time: 388ms
memory: 101328kb

input:

4996
1 2
2 3
1 4
4 5
4 6
3 7
4 8
8 9
3 10
9 11
5 12
7 13
12 14
8 15
8 16
14 17
10 18
15 19
17 20
15 21
19 22
21 23
14 24
20 25
25 26
21 27
20 28
19 29
29 30
24 31
31 32
29 33
27 34
34 35
31 36
27 37
30 38
35 39
38 40
37 41
34 42
41 43
43 44
42 45
36 46
37 47
47 48
47 49
41 50
50 51
46 52
50 53
51 54...

output:

4869
3419
3000
4640
4996
4996
3854
4165
4542
4996
1758
3584
3011
4996
4996
4383
2064
4199
2786
2470
4759
4996
4657
4157
2443
2594
1823
3215
1635
3908
1903
3207
2153
4448
4996
4996
3071
2649
3452
4996
1235
1599
2732
2244
2311
4618
1250
4577
3498
4941
1058
3498
3539
3415
907
4170
4996
4144
2235
2664
4...

result:

ok 4952 numbers

Test #6:

score: 0
Accepted
time: 179ms
memory: 99184kb

input:

4935
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50
5...

output:

4442
4133
346
3268
4850
3512
3312
3581
4092
4655
2256
3950
3157
3480
4935
4188
4935
1593
1135
4935
4935
4875
4108
3771
4158
4935
4935
3156
3148
1814
4935
3368
4303
2861
4917
2370
3992
4764
2772
4935
4935
2640
4935
4691
2291
4268
1798
4530
3058
3219
4935
3141
4935
2699
4547
2164
2495
3049
370
3409
21...

result:

ok 4992 numbers

Test #7:

score: 0
Accepted
time: 193ms
memory: 98376kb

input:

4919
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

2653
3219
4302
1418
1713
713
3341
647
487
1508
971
4851
4443
3078
2380
2267
4171
18
2056
1833
3136
817
4375
4103
3423
433
3967
725
282
2358
4171
1680
3350
2403
802
1855
137
2091
3731
1061
581
1273
4783
133
1911
4239
4233
678
3127
3481
284
1896
435
593
4781
103
4647
1615
1231
2689
574
1833
4783
645
4...

result:

ok 4980 numbers

Test #8:

score: 0
Accepted
time: 376ms
memory: 100456kb

input:

4973
1 4517
2 744
3 1115
4 3191
5 4186
6 4608
7 3898
8 3939
9 1998
10 2287
11 2277
12 4200
13 4935
14 3955
15 3683
16 278
17 547
18 3351
19 2642
20 4050
21 3457
22 2337
23 3435
24 1476
25 4853
26 3985
27 736
28 3016
29 4840
30 3866
31 4567
32 4067
33 3724
34 1872
35 1533
36 4787
37 53
38 1632
39 295...

output:

91
2487
2646
1791
2447
3327
532
1801
1079
1526
1236
77
4028
3401
4103
1573
3540
1641
452
52
2497
3128
2593
734
1293
3213
1786
1626
2130
2033
1935
2673
1758
1838
1284
758
2952
301
947
2875
3073
1462
2615
2842
3561
1969
1416
3088
2476
1082
696
3665
2041
3263
3063
2988
1402
1050
2967
3696
2309
3767
281...

result:

ok 4982 numbers

Subtask #2:

score: 0
Memory Limit Exceeded

Test #9:

score: 0
Memory Limit Exceeded

input:

199995
1 2
2 3
2 4
1 5
3 6
5 7
6 8
4 9
2 10
5 11
5 12
1 13
1 14
1 15
13 16
1 17
10 18
16 19
11 20
8 21
17 22
4 23
19 24
7 25
22 26
8 27
14 28
1 29
9 30
3 31
3 32
21 33
19 34
26 35
34 36
5 37
29 38
22 39
5 40
13 41
28 42
8 43
35 44
22 45
14 46
12 47
32 48
11 49
8 50
18 51
23 52
18 53
4 54
6 55
10 56
...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Memory Limit Exceeded

Test #25:

score: 0
Memory Limit Exceeded

input:

199991
1 2
2 3
3 4
3 5
5 6
3 7
1 8
8 9
8 10
10 11
1 12
1 13
13 14
4 15
12 16
13 17
17 18
8 19
3 20
9 21
16 22
10 23
1 24
7 25
6 26
12 27
4 28
21 29
27 30
30 31
21 32
19 33
20 34
17 35
7 36
13 37
24 38
37 39
30 40
31 41
15 42
9 43
32 44
41 45
18 46
38 47
8 48
35 49
13 50
35 51
47 52
35 53
48 54
44 55...

output:


result:


Subtask #5:

score: 0
Memory Limit Exceeded

Dependency #1:

100%
Accepted

Test #33:

score: 0
Memory Limit Exceeded

input:

49994
1 2
1 3
1 4
4 5
4 6
2 7
5 8
2 9
5 10
3 11
11 12
5 13
2 14
5 15
14 16
15 17
15 18
11 19
7 20
2 21
1 22
21 23
15 24
22 25
16 26
22 27
16 28
11 29
17 30
21 31
3 32
22 33
3 34
33 35
34 36
17 37
22 38
21 39
22 40
11 41
14 42
30 43
42 44
27 45
41 46
21 47
5 48
17 49
40 50
31 51
23 52
40 53
17 54
39 ...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%