QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468117#1163. Another Tree Queries Problem_log_WA 0ms7692kbC++148.2kb2024-07-08 19:23:412024-07-08 19:23:41

Judging History

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

  • [2024-07-08 19:23:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7692kb
  • [2024-07-08 19:23:41]
  • 提交

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: 0
Wrong Answer
time: 0ms
memory: 7692kb

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:


result:

wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements