QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733606#5020. 举办乘凉州喵,举办乘凉州谢谢喵londono0 1306ms217016kbC++148.3kb2024-11-10 20:04:472024-11-10 20:04:51

Judging History

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

  • [2024-11-10 20:04:51]
  • 评测
  • 测评结果:0
  • 用时:1306ms
  • 内存:217016kb
  • [2024-11-10 20:04:47]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = (int)2e5+5;

int n; vector<int> G[MAXN];

namespace LCA{
    const int stp = 17;
    int fa[MAXN][stp+1], dep[MAXN];

    void dfs_build(int x) {
        dep[x] ++;
        for (int i = 1; i <= stp; i++) {
            fa[x][i] = fa[fa[x][i-1]][i-1];
        }
        for (int to : G[x]) {
            if (to == fa[x][0]) continue;
            dep[to] = dep[x];
            fa[to][0] = x;
            dfs_build(to);
        }
    }

    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        for (int i = stp; i >= 0; i--) {
            if (dep[fa[x][i]] >= dep[y]) {
                x = fa[x][i];
            }
        }
        if (x == y) return x;
        for (int i = stp; i >= 0; i--) {
            if (fa[x][i] != fa[y][i]) {
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }

    int dist(int x, int y) {
        return dep[x]+dep[y]-2*dep[lca(x,y)];
    }
}

int m, ans[MAXN];
struct qr{ int d, k; int i;   }; 
vector<qr> qsf[MAXN], qf[MAXN], qg[MAXN];

namespace TSG{
    int fa[MAXN], hson[MAXN], dep[MAXN], siz[MAXN];
    void dfs1(int x) {
        dep[x] ++; siz[x] = 1;
        for (int to : G[x]) {
            if (to == fa[x]) continue;
            fa[to] = x; dep[to] = dep[x];
            dfs1(to);
            siz[x] += siz[to];
            if (siz[to] > siz[hson[x]]) {
                hson[x] = to;
            }
        }
    }

    int top[MAXN];
    void dfs2(int x, int tp) {
        top[x] = tp;
        for (int to : G[x]) {
            if (to == fa[x]) continue;
            dfs2(to, (to==hson[x]?tp:to));
        }
    }

    void addRF(int x, int d, int k, int i) {
        ans[i] += LCA::dep[x];
        qg[x].push_back({d, k, i});
        if (d == 0) return;

        if (hson[x] && d)
            qf[hson[x]].push_back({d-1, k, i});
        while (1) {
            x = top[x];
            if (x == 1) break;
            qf[x].push_back({d-1, -k, i});
            qf[hson[fa[x]]].push_back({d-1, k, i});
            x = fa[x];
        }
    }
}

void init() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

void addSF(int x, int d, int k, int i) {
    qsf[x].push_back({d, k, i});
}

void dealqry() {
    cin >> m;
    for (int i = 1, u, v, d, t; i <= m; i++) {
        cin >> u >> v >> d;
        t = LCA::lca(u, v);
        TSG::addRF(u, d, 1, i);
        TSG::addRF(v, d, 1, i);
        TSG::addRF(t, d, -2, i);
        addSF(t, d, 1, i);
    }
}

namespace getf{
    const int MAXL = MAXN*20*2;
    int rt[MAXN];
    int sum[MAXL], lc[MAXL], rc[MAXL], pt;

    void modify(int p, int l, int r, int x, int v) {
        sum[p] += v;
        if (l == r) return;
        int mid = l + r >> 1;
        if (x <= mid) {
            if (!lc[p]) lc[p] = ++pt;
            modify(lc[p], l, mid, x, v);
        } else {
            if (!rc[p]) rc[p] = ++pt;
            modify(rc[p], mid+1, r, x, v);
        }
    }
    int merge(int p, int q, int l, int r) {
        if (!p || !q) return p | q;
        int mid = l + r >> 1;
        sum[p] += sum[q];
        lc[p] = merge(lc[p], lc[q], l, mid);
        rc[p] = merge(rc[p], rc[q], mid+1, r);
        return p;
    }
    int query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[p];
        int mid = l + r >> 1, res = 0;
        if (ql <= mid) res += query(lc[p], l, mid, ql, qr);
        if (mid < qr) res += query(rc[p], mid+1, r, ql, qr);
        return res;
    }

    void calc(int x, int fa, int dep) {
        rt[x] = ++pt;
        modify(rt[x], 1, n, dep, 1);
        for (int to : G[x]) {
            if (to == fa) continue;
            calc(to, x, dep+1);
            rt[x] = merge(rt[x], rt[to], 1, n);
        }

        for (qr _ : qf[x]) {
            ans[_.i] += query(rt[x], 1, n, dep, dep+_.d) * _.k;
        }
    }
}
namespace getg{
    #define lowbit(x) ((x)&-(x))
    struct arr{
        int t[MAXN], d[MAXN], ti;
        int& operator [] (int x) {
            if (t[x] != ti) {
                t[x] = ti;
                d[x] = 0;
            }
            return d[x];
        }
    }bit;

    void mdf(int x, int v) {
        for (; x <= n; x+=lowbit(x)) {
            bit[x] += v;
        }
    }
    int qry(int x) {
        int sum = 0;
        for (; x; x-=lowbit(x))
            sum += bit[x];
        return sum;
    }

    void insert(int x, int fa, int dep) {
        mdf(dep, 1);
        for (int to : G[x]) {
            if (to == fa) continue;
            insert(to, x, dep+1);
        }
    }

    void calc(int x, int fa, int dep) {
        bit.ti++;
        for (int to : G[x]) {
            if (to == fa || to == TSG::hson[x]) continue;
            insert(to, x, 1);
        }
        for (qr _ : qf[x]) {
            ans[_.i] += qry(_.d)*_.k;
        }

        for (int to : G[x]) {
            if (to == fa) continue;
            calc(to, x, dep+1);
        }
    }
}
namespace getsf{
    #define vi vector<int>
    bool vis[MAXN];
    int siz[MAXN], all;

    void dfssiz(int x, int fa) {
        siz[x] = 1;
        for (int to : G[x]) {
            if (to == fa || vis[to]) continue;
            dfssiz(to, x);
            siz[x] += siz[to];
        }
    }
    int dfsmid(int x, int fa) {
        int mx = all - siz[x];
        for (int to : G[x]) {
            if (to == fa || vis[to]) continue;
            int tmp = dfsmid(to, x);
            if (tmp) return tmp;
            mx = max(mx, siz[to]);
        }
        return x*(mx*2<=all);
    }

    int Tfa[MAXN];
    int findmid(int x) {
        dfssiz(x, 0);
        all = siz[x];
        return dfsmid(x, 0);
    }

    vi b[MAXN], fb[MAXN];
    void mdf(vi& bit, int x, int v) {
        for (; x < bit.size(); x+=lowbit(x)) {
            bit[x] += v;
        }
    }
    int qry(vi& bit, int x) {
        int res = 0;
        for (; x; x-=lowbit(x)) {
            res += bit[x];
        }
        return res;
    }

    int dfs_mxdep(int x, int fa) {
        int res = 0;
        for (int to : G[x]) {
            if (to == fa || vis[to]) continue;
            res = max(res, dfs_mxdep(to, x));
        }
        return res+1;
    }
    void insert(vi v, int x, int fa, int dep) {
        mdf(v, dep, 1);
        for (int to : G[x]) {
            if (to == fa || vis[to]) continue;
            insert(v, to, x, dep+1);
        }
    }
    void build(int x) {
        vis[x] = 1;

        b[x].resize(dfs_mxdep(x, 0)+1);
        insert(b[x], x, 0, 1);

        for (int to : G[x]) {
            if (vis[to]) continue;
            int tr = findmid(to);
            Tfa[tr] = x;
            fb[tr].resize(dfs_mxdep(to, 0)+1);
            insert(fb[tr], to, 0, 2);
            build(tr);
        }
    }

    void calc() {
        build(findmid(1));
        for (int i = 1; i <= n; i++) {
            if (qsf[i].empty()) continue;
            int now = i, pre = 0;
            while (now) {
                for (qr _ : qsf[i]) {
                    int nd = _.d - LCA::dist(now, i);
                    if (nd < 0) continue;
                    ans[_.i] += qry(b[now], nd+1)*_.k;
                    if (pre) ans[_.i] -= qry(fb[pre], nd+1);
                }
                pre = now; now = Tfa[now];
            }
        }
    }
}

void print() {
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    // g++ code.cpp -o code.exe -std=c++14 -O2 -fno-ms-extensions "-Wl,--stack=1000000000" -DLOCAL; ./code
    time_t stm = clock();

    #ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("ans.out", "w", stdout);
    #else
    // freopen("tii.in", "r", stdin);
    // freopen("tii.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #endif

    init();
    LCA::dfs_build(1);
    TSG::dfs1(1);
    TSG::dfs2(1, 1);
    dealqry();
    getf::calc(1, 1, 1);
    getg::calc(1, 1, 1);
    getsf::calc();
    print();

    cerr << "Exec Time: " << (double)(clock()-stm)/CLOCKS_PER_SEC << "s" << endl;
    return 0;
}

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

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:

-1090
-763
-4573
16
0
-2293
-1926
-635
-4028
-138
9
36
-3310
3
-1194
-1379
-3759
60
-3326
14
-335
-1138
-4280
-2358
21
17
-4670
-1742
12
-1603
7
-813
48
-210
28
-1618
-185
-32
19
-791
-1592
13
19
-2372
-4024
-10
-3349
-3477
22
-36
14
8
5
-646
-3907
-2624
17
-755
-8
14
-599
-30
-3458
-6
-1868
-400
17...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1306ms
memory: 217016kb

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:

33
86
47
-37
106
39
52
76
53
1
89
66
36
-3
58
11
21
73
-5
37
33
112
33
114
-28
30
31
1
144
-2
-81
2003493398
33
65
42
36
21
39
-8
69
-9
64
-15
4
4
49
164
59
6169
-2010191759
42
51
36
17
108
9
59
89
61
45
113
49
34
36
37
28
30
63
-1999144876
31
114
-19
72
78
61
42
58
73
24
15
56
36
2005150143
21
9169...

result:

wrong answer 1st numbers differ - expected: '757', found: '33'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1121ms
memory: 192744kb

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:

16
-31028
-29135
-555
-41248
-44334
-1211
-43998
24
-1373
23
19
5
-127919
27
-114622
-1
-133410
-26178
-793
-36589
-14205
23
-91332
-7122
42
-23030
-7933
-31519
27
-94734
33
23
-44300
-189
-503
-44444
-81344
-3
-33976
-71967
-128849
-2402
-4571
-21516
-102663
-29071
17
25
-69
-145633
-90001
-4839
-1...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%