QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468108#1163. Another Tree Queries Problem_log_TL 0ms7812kbC++148.2kb2024-07-08 19:22:062024-07-08 19:22:10

Judging History

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

  • [2024-07-08 19:22:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7812kb
  • [2024-07-08 19:22:06]
  • 提交

answer

# include <bits/stdc++.h>
# define rep(i, j, k) for(int i = j; i <= k; ++i)
# define maxn 200100
using namespace std;

int n, q, ans1, ans2;
int op, t1, t2;

namespace Debug {
    bool Ratio;
} using namespace Debug;

namespace Little_Function {
    inline int calc(int l, int r) {return (l + r) * (r - l + 1) / 2;}
    inline bool check(int x, int l, int r) {return l <= x && x <= r;}
} using namespace Little_Function;

namespace Tree {
    # define go(u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
    int head[maxn], to[maxn], nxt[maxn], tot;
    int fa[maxn], dep[maxn], siz[maxn], son[maxn];
    int dfn[maxn], dfn1[maxn], top[maxn], stp;
    int sdep[maxn], ssiz[maxn];

    inline void add_edge(int u, int v) {
        nxt[++tot] = head[u]; to[tot] = v; head[u] = tot;
        nxt[++tot] = head[v]; to[tot] = u; head[v] = tot;
    }

    void dfs(int u, int fat) {
        int Max = -1; fa[u] = fat; dep[u] = dep[fat] + 1; siz[u] = 1;
        go(u) if(v != fat) dfs(v, u), son[u] = siz[v] > Max ? v : son[u], Max = siz[son[u]], sdep[u] += sdep[v], siz[u] += siz[v];
        sdep[u] += dep[u];
    }

    void dfs2(int u, int tp) {
        dfn[u] = ++stp; dfn1[stp] = u; top[u] = tp; ssiz[dfn[u]] = siz[u];
        if(son[u]) dfs2(son[u], tp);
        go(u) if(!dfn[v]) dfs2(v, v);
    }

    inline int Lca(int x, int y) {
        while(top[x] != top[y]) dep[top[x]] < dep[top[y]] ? y = fa[top[y]] : x = fa[top[x]];
        return dep[x] < dep[y] ? x : y;
    }
} using namespace Tree;

namespace Segment_Tree {
    # define lc(p) (p << 1)
    # define rc(p) (p << 1 | 1)
    # define mid (pl + pr >> 1)
    # define slen (pr - pl + 1)
    # define llen (mid - pl + 1)
    # define rlen (pr - mid)
    # define push_up(p) tree[p] = tree[p << 1] + tree[p << 1 | 1]
    int tree[maxn], sum[maxn], tag[maxn], up[maxn];

    inline void push_down(int p, int pl, int pr) {
        tree[lc(p)] += up[p] * calc(rlen + 1, slen); tree[rc(p)] += up[p] * calc(1, rlen);
        up[lc(p)] += up[p]; up[rc(p)] += up[p]; up[p] = 0; sum[lc(p)] += rlen * up[p];
        tree[lc(p)] += sum[p] * llen; tree[rc(p)] += sum[p] * rlen;
        sum[lc(p)] += sum[p]; sum[rc(p)] += sum[p]; sum[p] = 0;
        tree[lc(p)] += tag[p] * (ssiz[mid] - ssiz[pl - 1]); tree[rc(p)] += tag[p] * (ssiz[pr] - ssiz[mid]);
        tag[lc(p)] += tag[p]; tag[rc(p)] += tag[p]; tag[p] = 0;
    }

    void update(int p, int pl, int pr, int l, int r, int x) {
        if(Ratio) cout << "update receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << ' ' << x << '\n';
        if(l <= pl && pr <= r) {sum[p] += x; tree[p] += x * slen;/* cout << p << ' ' << tree[p] << ' ' << x << '\n'; */return;}
        // cout << p << ' ' << pl << ' ' << pr << ' ' << tree[5] << '\n';
        push_down(p, pl, pr);
        // cout << p << ' ' << pl << ' ' << pr << ' ' << tree[5] << '\n';
        if(l <= mid) update(lc(p), pl, mid, l, r, x);
        if(r > mid) update(rc(p), mid + 1, pr, l, r, x);
        push_up(p);
        // cout << p << ' ' << tree[p] << ' ' << x << '\n';
    }

    void update1(int p, int pl, int pr, int l, int r, int x) {
        if(Ratio) cout << "update1 receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << ' ' << x << '\n';
        if(l <= pl && pr <= r) {tag[p] += x; tree[p] += x * (ssiz[pr] - ssiz[pl - 1]); return;}
        push_down(p, pl, pr);
        if(l <= mid) update1(lc(p), pl, mid, l, r, x);
        if(r > mid) update1(rc(p), mid + 1, pr, l, r, x);
        push_up(p);
    }

    void update2(int p, int pl, int pr, int l, int r) {
        if(Ratio) cout << "update2 receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << '\n';
        if(l <= pl && pr <= r) {up[p]++; sum[p] += r - pr; tree[p] += calc(1, slen) + (r - pr) * slen; return;}
        push_down(p, pl, pr);
        if(l <= mid) update2(lc(p), pl, mid, l, r);
        if(r > mid) update2(rc(p), mid + 1, pr, l, r);
        push_up(p);
    }

    int query(int p, int pl, int pr, int l, int r) {
        if(l <= pl && pr <= r) return tree[p];
        push_down(p, pl, pr); int sum = 0;
        if(l <= mid) sum += query(lc(p), pl, mid, l, r);
        if(r > mid) sum += query(rc(p), mid + 1, pr, l, r);
        return sum;
    }

    void print(int p, int pl, int pr, bool flag) {
        if(flag)
            cout << p << ' ' << pl << ' ' << pr << ' ' << tree[p] << ' ' << sum[p] << ' ' << tag[p] << ' ' << up[p] << '\n';
        else
            cerr << p << ' ' << pl << ' ' << pr << ' ' << tree[p] << ' ' << sum[p] << ' ' << tag[p] << ' ' << up[p] << '\n';
        if(pl != pr) print(lc(p), pl, mid, flag), print(rc(p), mid + 1, pr, flag);            
    }
} using namespace Segment_Tree;

namespace Query {
    void modify1(int u, int v) {
        ans1 += siz[v]; ans2 += sdep[v];
        update1(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, 1);
        int pos = fa[u];
        while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], siz[v]), pos = fa[top[pos]];
    }

    void modify2(int u, int v) {
        int pos = u;
        if(!check(u, dfn[v] + 1, dfn[v] + siz[son[v]])) while(top[pos] != top[v]) {
            pos = top[pos];
            if(fa[pos] == v) break;
            else pos = fa[pos];
        }
        else pos = dfn1[dfn[v] + 1];
        ans1 += n - siz[pos], ans2 += sdep[1] - sdep[pos];
        update1(1, 1, n, 1, n, 1); update1(1, 1, n, dfn[pos], dfn[pos] + siz[pos] - 1, -1);
        while(v != 0) update(1, 1, n, dfn[top[v]], dfn[v], -siz[pos]), v = fa[top[v]];
    }

    void modify3(int u, int v) {
        int len = 0, pos = fa[v]; ans1 += dep[u] - dep[v] + 1; ans2 += calc(dep[v], dep[u]);
        while(top[u] != top[v]) {
            // cout << "kkk\n";
            update(1, 1, n, dfn[top[u]], dfn[u], len); update2(1, 1, n, dfn[top[u]], dfn[u]);
            u = fa[top[u]]; len += dfn[u] - dfn[top[u]] + 1;
        }
        // if(Ratio) cout << "\n\n";
        // if(Ratio) cout << "\na\n";
        // if(Ratio) cout << "a\n" << len << '\n';
        update(1, 1, n, dfn[v], dfn[u], len);
        // if(Ratio) cout << "\n\n";
        // if(Ratio) print(1, 1, n, 1);
        // if(Ratio) cout << "\n\n" << u << ' ' << v << ' ' << dfn[u] << ' ' << dfn[v] << '\n';
        // if(Ratio) cout << "b\n";
        update2(1, 1, n, dfn[v], dfn[u]);
        // if(Ratio) print(1, 1, n, 1);
        // if(Ratio) cout << "\n\n";
        // if(Ratio) cout << "c " << u << ' ' << v << '\n';
        while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], dep[u] - dep[v] + 1), pos = fa[top[pos]];
        // if(Ratio) cout << "chenzhe\n", print(1, 1, n, 1); cout << "\n\n";
    }

    void modify4(int u, int v) {
        int lca = Lca(u, v), pos = lca;
        // if(Ratio) print(1, 1, n, 1); cout << "\n\n";
        modify3(u, lca); modify3(v, lca); ans2 -= dep[lca]; ans1--;
        // if(Ratio) print(1, 1, n, 1); cout << "\n\n";
        while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], -1), pos = fa[top[pos]];
    }

    int query(int u) {
        int sum = 0, pos = u;
        while(pos != 0) sum += Segment_Tree::query(1, 1, n, dfn[top[pos]], dfn[pos]), pos = fa[top[pos]];
        // cout << ans1 << ' ' << ans2 << ' ' << sum << ' ' << dep[u] << ' ' << u << '\n';
        return dep[u] * ans1 + ans2 - sum * 2;
    }
} using namespace Query;

# define debug cerr << "I Love Furina Forever", exit(0)

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, 1, n - 1) cin >> t1 >> t2, add_edge(t1, t2);
    dfs(1, 0); dfs2(1, 1);
    // debug;
    cin >> q;
    rep(i, 1, q) {
        cin >> op >> t1; if(op != 3) cin >> t2;
        // if(i == 3) Ratio = 1;/
        if(op == 1) {
            if(check(t1, dfn[t2], dfn[t2] + siz[t2] - 1)) modify2(t1, t2);
            else modify1(t1, t2);
        }
        if(op == 2) {
            if(dep[t1] < dep[t2]) swap(t1, t2);
            modify4(t1, t2);
        }
        if(op == 3) {
            // cout << op << ' ' << t1 << '\n';
            cout << query(t1) << '\n';
        }
        // cerr << "Time = " << i << '\n';
        // print(1, 1, n, 0);
        // cerr << "\n\n"; cout << "\n\n";
        // Ratio = 0;
        // debug;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7812kb

input:

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

output:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: -100
Time Limit Exceeded

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:


result: