QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137598#5020. 举办乘凉州喵,举办乘凉州谢谢喵ckiseki0 714ms202196kbC++239.4kb2023-08-10 14:23:422023-08-10 14:23:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 14:23:45]
  • 评测
  • 测评结果:0
  • 用时:714ms
  • 内存:202196kb
  • [2023-08-10 14:23:42]
  • 提交

answer

// An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

using lld = int64_t;

struct Centroid {
    vector<vector<int>> &g;
    vector<vector<pair<int, lld&>>> qs;
    vector<int> vis, sz;
    vector<int> dis;
    Centroid(vector<vector<int>> &t_g) : g(t_g), qs(g.size()),
        vis(g.size()), sz(g.size()), dis(g.size()) {
    }
    void solve() {
        decomp(0, 0);
    }
    void add_query(int i, int d, lld &a) {
        qs[i].emplace_back(d, a);
    }

    void get_size(vector<int> &s, int i) {
        s.emplace_back(i);
        vis[i] = true;
        sz[i] = 1;
        for (int j: g[i]) if (!vis[j]) {
            get_size(s, j);
            sz[i] += sz[j];
        }
    }
    void dfs(vector<int> &s, int i) {
        s.emplace_back(i);
        vis[i] = true;
        for (int j: g[i]) if (!vis[j]) {
            dis[j] = dis[i] + 1;
            dfs(s, j);
        }
    }

    void gao(const vector<int> &vtx, int coef) {
        int mx = 0;
        for (int x: vtx) mx = max(mx, dis[x]);
        vector<int> pre(mx + 1);
        for (int x: vtx) {
            pre[dis[x]] += 1;
            mx = max(mx, dis[x]);
        }
        for (int i = 1; i <= mx; i++) pre[i] += pre[i - 1];
        for (int x: vtx) {
            for (auto &[d, p]: qs[x]) {
                // #{ y | dis[x] + dis[y] <= d }
                int cnt = d - dis[x] < 0 ? 0 : pre[min(mx, d - dis[x])];
                p += coef * cnt;
            }
        }
    }

    void decomp(int i, int d) {
        vector<int> s;
        get_size(s, i);
        int c = -1;
        for (int j: s) {
            if (sz[j] * 2 >= sz[i])
                c = j;
            vis[j] = false;
        }
        vis[c] = true;

        vector<int> total;
        vector<vector<int>> sub;
        for (int j: g[c]) {
            if (vis[j]) continue;
            dis[j] = 1;
            sub.emplace_back();
            dfs(sub.back(), j);
            for (int x: sub.back())
                total.emplace_back(x);
        }
        dis[c] = 0;
        total.emplace_back(c);

        gao(total, 1);
        for (const auto &t: sub) gao(t, -1);

        for (int j: s) vis[j] = false;
        vis[c] = true;
        for (int j: g[c]) {
            if (vis[j]) continue;
            decomp(j, d + 1);
        }
    }
};

struct HLD {
    vector<vector<int>> &g;
    vector<vector<tuple<int, int, lld&>>> g_qs;
    vector<vector<tuple<int, int, lld&>>> f_qs;

    vector<int> vis, sz, mxs, top, pa, dep;
    int dfc;
    vector<int> tin, tou, ord;
    int64_t totsum;
    vector<int64_t> sum;
    HLD(vector<vector<int>> &t_g) : g(t_g),
        g_qs(g.size()), f_qs(g.size()),
        vis(g.size()), sz(g.size()), mxs(g.size()), top(g.size()), pa(g.size()), dep(g.size()),
        dfc(0), tin(g.size()), tou(g.size()), ord(g.size()),
        totsum(0), sum(g.size() + 1) {
        get_size(0, -1);
        make_chain(0, -1, 0);
    }
    void get_size(int i, int f) {
        pa[i] = f;
        sz[i] = 1; mxs[i] = -1;
        for (int j: g[i]) {
            if (j == f) continue;
            dep[j] = dep[i] + 1;
            get_size(j, i);
            sz[i] += sz[j];
            if (mxs[i] == -1 || sz[mxs[i]] < sz[j])
                mxs[i] = j;
        }
    }
    void make_chain(int i, int f, int t) {
        ord[dfc] = i;
        tin[i] = dfc++;
        top[i] = t;
        if (mxs[i] != -1) make_chain(mxs[i], i, t);
        for (int j: g[i]) {
            if (j == f) continue;
            if (j == mxs[i]) continue;
            make_chain(j, i, j);
        }
        tou[i] = dfc;
    }

    void add_f_query(int u, int d, int coef, lld &ans) {
        debug("ADD_F_QUERY", u+1, d, coef);
        if (d < 0) return;
        ans += coef * sz[u];
        f_qs[tou[u]-1].emplace_back(dep[u] + d + 1, -coef, ans);
        f_qs[tin[u]].emplace_back(dep[u] + d + 1, coef, ans);
        // int cnt = 0;
        // for (int t = tin[u]; t < tou[u]; t++) {
        //     int v = ord[t];
        //     if (dep[v] - dep[u] <= d) ++cnt;
        // }
        // debug(u+1, d, coef, cnt);
        // ans += coef * cnt;
    }

    void do_f_query(int n) {
        vector<int64_t> cnt(n);
        for (int i = 0; i < n; i++) {
            cnt[ dep[ord[i]] ] += sz[ord[i]];
            for (auto &[d, coef, ans]: f_qs[i])
                ans += coef * (d >= 0 && d < n ? cnt[d] : 0);
        }
    }

    int add_query(int x, int y, int d, lld &ans) {
        g_qs[x].emplace_back(d, 1, ans);
        g_qs[y].emplace_back(d, 1, ans);
        for (int w: {x, y})
            if (mxs[w] != -1)
                add_f_query(mxs[w], d - 1, 1, ans);
        int org_x = x, org_y = y;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            int t = top[x];
            add_f_query(t, d - 1, -1, ans);
            add_f_query(mxs[pa[t]], d - 1, 1, ans);
            x = pa[t];
        }
        int z = dep[x] < dep[y] ? x : y;
        if (pa[z] != -1)
            g_qs[pa[z]].emplace_back(d, -2, ans);
        add_f_query(z, d, -2, ans);
        int onchain = dep[org_x] + dep[org_y] - dep[z] * 2 + 2;
        ans += onchain;
        debug(onchain);
        return z;
    }


    void dfs_g(int i, int f) {
        if (mxs[i] != -1) {
            totsum += sz[i] - 1 - sz[mxs[i]];
            for (int t = tou[mxs[i]]; t < tou[i]; t++) {
                int u = ord[t];
                sum[ dep[u] - dep[i] ] += sz[u];
            }
        }

        for (auto &[d, coef, ans]: g_qs[i]) {
            // for (int x = i; x != -1; x = pa[x]) {
            //     int m = 0;
            //     if (mxs[x] != -1)
            //         for (int t = tou[mxs[x]]; t < tou[x]; t++) {
            //             int u = ord[t];
            //             debug(u);
            //             if (dep[u] - dep[x] == d + 1)
            //                 m += sz[u];
            //         }
            //     debug(x+1, sz[x] - 1 - m, sz[x], m);
            // }
            debug(totsum, sum[d + 1]);
            int64_t cur = totsum - sum[d + 1];
            debug(coef, cur, d, i+1);
            ans += coef * cur;
        }

        for (int j: g[i]) {
            if (j == f) continue;
            dfs_g(j, i);
        }

        if (mxs[i] != -1) {
            totsum += sz[i] - 1 - sz[mxs[i]];
            for (int t = tou[mxs[i]]; t < tou[i]; t++) {
                int u = ord[t];
                sum[ dep[u] - dep[i] ] += sz[u];
            }
        }
    }

    void solve() {
        dfs_g(0, -1);
        do_f_query(g.size());
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }


    int q;
    cin >> q;
    vector<lld> ans(q);
    Centroid cent(g);
    HLD hld(g);

    /* const auto brute = [&](int x, int y, int d) { */
    /*     const auto &p = hld.pa; */
    /*     const auto &dep = hld.dep; */
    /*     vector<int> dis(n, -1); */
    /*     queue<int> que; */
    /*     while (x != y) { */
    /*         if (dep[x] < dep[y]) swap(x, y); */
    /*         que.emplace(x); */
    /*         dis[x] = 0; */
    /*         x = p[x]; */
    /*     } */
    /*     que.emplace(x); */
    /*     dis[x] = 0; */
    /*     while (!que.empty()) { */
    /*         int i = que.front(); que.pop(); */
    /*         for (int j: g[i]) { */
    /*             if (dis[j] == -1) { */
    /*                 dis[j] = dis[i] + 1; */
    /*                 que.emplace(j); */
    /*             } */
    /*         } */
    /*     } */
    /*     int a = 0; */
    /*     for (int i = 0; i < n; i++) */
    /*         if (dis[i] <= d) */
    /*             ++a; */
    /*     return a; */
    /* }; */
    /* vector<lld> bans(q); */

    for (int i = 0; i < q; i++) {
        // int x = rand() % n;
        // int y = rand() % n;
        // int d = rand() % n;
        int x, y, d;
        cin >> x >> y >> d;
        --x, --y;

        // bans[i] = brute(x, y, d);
        int z = hld.add_query(x, y, d, ans[i]);
        cent.add_query(z, d, ans[i]);
        // hld.add_query(z, d, -2, ans[i]);
        // hld.add_query(x, d, 1, ans[i]);
        // hld.add_query(y, d, 1, ans[i]);
    }

    hld.solve();
    orange(all(ans));

    cent.solve();

    orange(all(ans));
    // orange(all(bans));
    // assert (ans == bans);

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 7472kb

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:

30010
17140
21702
2194
6418
7306
28872
21601
32634
17754
7662
21443
34308
9588
46728
41946
7588
36201
34311
12
22170
20913
28544
22488
19
7076
26816
39684
9202
17294
6304
19265
26992
27060
3697
25842
19231
1274
5814
43252
27008
5244
4693
29047
31316
19542
30230
31008
5167
9210
6463
5475
11401
19993
...

result:

wrong answer 1st numbers differ - expected: '3226', found: '30010'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 552ms
memory: 83072kb

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:

757
69428
2793
181264
91707
318
32496
199183
6399
15983
11640
119051
236
689
15
9532
41
36592
181376
56
45524
193451
90248
3417
1313
112
34413
60471
199861
188090
75092
127
1
6
4
3
443
11
61157
199860
199153
155706
196287
193374
53802
51978
179199
428
196282
199989
3613
26
99007
134461
198159
20382
...

result:

wrong answer 6th numbers differ - expected: '182', found: '318'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 714ms
memory: 202196kb

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:

279516
1237251
2658896
868154
1023681
1311194
125846
2021344
7963
588685
149035
132964
295518
1999451
25
1254148
484609
1954228
2641113
643071
2561429
423969
74777
2003130
1554764
380145
340714
2255199
2625525
8160
2368266
351995
111214
2340882
260295
357053
1309394
1440746
278649
1402744
1399289
19...

result:

wrong answer 1st numbers differ - expected: '78', found: '279516'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%