Starters 212-Beautiful Sum

思路讲解

AC代码

https://www.codechef.com/viewsolution/1209777968

源代码

// by Gospel_rock
// title: Beautiful Sum
// url: https://www.codechef.com/problems/XPS

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;
using ll = long long;

static constexpr int LOG = 21;

// --- 核心数据结构 ---

struct Tag {
    ll xor_val[2]; // [0]:偶深, [1]:奇深
    explicit Tag(ll e=0, ll o=0) { xor_val[0] = e; xor_val[1] = o; }
    void apply(const Tag &t) { xor_val[0] ^= t.xor_val[0]; xor_val[1] ^= t.xor_val[1]; }
    bool empty() const { return xor_val[0] == 0 && xor_val[1] == 0; }
};

struct Info {
    int cnt[2];         // cnt[0]:偶深节点数, cnt[1]:奇深
    int bit_num[2][LOG]; // bit_num[0][i]: 偶深节点第i位为1的个数

    Info() { memset(cnt, 0, sizeof(cnt)); memset(bit_num, 0, sizeof(bit_num)); }

    // 初始化结构（奇偶性）
    static Info make_structure(int depth) {
        Info res;
        res.cnt[depth & 1] = 1;
        return res;
    }

    static Info merge(const Info &l, const Info &r) {
        Info res;
        FOR(p, 0, 1) {
            res.cnt[p] = l.cnt[p] + r.cnt[p];
            FOR(i, 0, LOG-1) res.bit_num[p][i] = l.bit_num[p][i] + r.bit_num[p][i];
        }
        return res;
    }

    void apply(const Tag &t) {
        FOR(p, 0, 1) {
            if (t.xor_val[p] == 0) continue;
            FOR(i, 0, LOG-1) {
                if ((t.xor_val[p] >> i) & 1) bit_num[p][i] = cnt[p] - bit_num[p][i];
            }
        }
    }
    static Info zero() { return Info(); }
};

// --- ZKW 线段树 ---
struct SEG {
    int n, sz, dep;
    vector<Info> info;
    vector<Tag> tag;

    SEG(int n_) {
        n = n_ + 2;
        dep = __lg(n) + 1;
        sz = 1 << dep;
        info.assign(sz * 2 + 5, Info());
        tag.assign(sz * 2 + 5, Tag());
    }

    static void pull(Info &fa, const Info &lc, const Info &rc) {
        fa = Info::merge(lc, rc);
    }
    void apply_one(int o, const Tag &t) {
        info[o].apply(t);
        tag[o].apply(t);
    }
    void pushdown(int o) {
        if (tag[o].empty()) return;
        int l = o << 1, r = l | 1;
        apply_one(l, tag[o]);
        apply_one(r, tag[o]);
        tag[o] = Tag();
    }
    void assign_raw(int i, const Info &v) { info[i + sz] = v; }
    void build() {
        for (int o = sz - 1; o >= 1; --o)
            pull(info[o], info[o << 1], info[o << 1 | 1]);
    }
    void push_path(int l, int r) {
        l = l - 1 + sz; r = r + 1 + sz;
        int i = dep, j = __lg(l ^ r);
        while (i > j) pushdown(l >> i--);
        while (i) { pushdown(l >> i); pushdown(r >> i); --i; }
    }
    Info query(int L, int R) {
        if (L > R) return Info::zero();
        push_path(L, R);
        int l = L - 1 + sz, r = R + 1 + sz;
        Info left = Info::zero(), right = Info::zero();
        for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) left = Info::merge(left, info[l ^ 1]);
            if (r & 1)  right = Info::merge(info[r ^ 1], right);
        }
        return Info::merge(left, right);
    }
    void range_apply(int L, int R, const Tag &t) {
        if (L > R) return;
        push_path(L, R);
        int l = L - 1 + sz, r = R + 1 + sz;
        int L0 = l, R0 = r; 
        for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) apply_one(l ^ 1, t);
            if (r & 1)  apply_one(r ^ 1, t);
        }
        for (L0 >>= 1; L0; L0 >>= 1) pull(info[L0], info[L0 << 1], info[L0 << 1 | 1]);
        for (R0 >>= 1; R0; R0 >>= 1) pull(info[R0], info[R0 << 1], info[R0 << 1 | 1]);
    }
};

// --- HLD ---
struct HLD {
    int n, cur;
    vector<vector<int>> g;
    vector<int> fa, dep, heavy, head, dfn, siz;

    HLD(int n_) : n(n_), cur(0), g(n_ + 1), fa(n_ + 1), dep(n_ + 1), heavy(n_ + 1), head(n_ + 1), dfn(n_ + 1), siz(n_ + 1) {}

    void addEdge(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
    int dfs1(int u, int f) {
        fa[u] = f; dep[u] = dep[f] + 1; siz[u] = 1;
        int maxsz = 0;
        for (int v : g[u]) if (v != f) {
            int sub = dfs1(v, u);
            siz[u] += sub;
            if (sub > maxsz) { maxsz = sub; heavy[u] = v; }
        }
        return siz[u];
    }
    void dfs2(int u, int h) {
        head[u] = h; dfn[u] = ++cur;
        if (heavy[u]) dfs2(heavy[u], h);
        for (int v : g[u]) if (v != fa[u] && v != heavy[u]) dfs2(v, v);
    }
    void build(int root = 1) { cur = 0; dfs1(root, 0); dfs2(root, root); }
    
    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (dep[head[u]] > dep[head[v]]) u = fa[head[u]];
            else v = fa[head[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    template<class F> void for_subtree(int u, F &&op) { op(dfn[u], dfn[u] + siz[u] - 1); }
    template<class F> void for_path(int u, int v, F &&op) {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) swap(u, v);
            op(dfn[head[u]], dfn[u]);
            u = fa[head[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        op(dfn[u], dfn[v]);
    }
};

struct HLDZKW {
    HLD hld;
    SEG seg;

    HLDZKW(int n) : hld(n), seg(n) {}
    void addEdge(int u, int v) { hld.addEdge(u, v); }

    void build() {
        hld.build(1);
        FOR(i, 1, hld.n) seg.assign_raw(hld.dfn[i], Info::make_structure(hld.dep[i]));
        seg.build();
    }

    void applySubtreeNode(int u, const Tag &t) {
        hld.for_subtree(u, [&](int L, int R) { seg.range_apply(L, R, t); });
    }
    void applyPathNode(int u, int v, const Tag &t) {
        hld.for_path(u, v, [&](int L, int R) { seg.range_apply(L, R, t); });
    }
    Info querySubtreeNode(int u) {
        Info res = Info::zero();
        hld.for_subtree(u, [&](int L, int R) { res = Info::merge(res, seg.query(L, R)); });
        return res;
    }
    Info queryPathNode(int u, int v) {
        Info res = Info::zero();
        hld.for_path(u, v, [&](int L, int R) { res = Info::merge(res, seg.query(L, R)); });
        return res;
    }

    // Top-Down Edge 接口
    void applySubtreeEdge(int u, const Tag &t) {
        applySubtreeNode(u, t); 
        int pos = hld.dfn[u];
        seg.range_apply(pos, pos, t); // 撤销 u (u代表u上方的边，不在子树边集中)
    }
};

void Solve(){
    ll N;
    cin >> N;
    vector<array<ll, 3>> edges;
    HLDZKW hld(N);
    
    FOR(i, 1, N - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        hld.addEdge(u, v);
        edges.push_back({u, v, w});
    }

    hld.build();

    // 初始化
    for (auto [u, v, w] : edges) {
        // 边 (u, v) 挂在儿子上。Node 操作代表子树下所有点路径 +w
        // 这里用 applySubtreeNode 是最自然的
        ll child = (hld.hld.dep[u] < hld.hld.dep[v]) ? v : u;
        hld.applySubtreeNode(child, Tag(w, w));
    }

    ll Q;
    cin >> Q;
    FOR(_, 1, Q) {
        ll opt;
        cin >> opt;
        if (opt == 1) {
            ll u, x;
            cin >> u >> x;
            Tag t;
            if (hld.hld.dep[u] % 2 == 0) t = Tag(0, x);
            else t = Tag(x, 0);
            
            // Q1: 修改子树内的边 -> 使用 Edge 接口 (排除 u)
            hld.applySubtreeEdge(u, t);
        } else {
            ll u;
            cin >> u;
            
            // --- 你的逻辑 ---
            // 1. 查 u 到根的路径异或和 D(u)
            Info u_to_root = hld.queryPathNode(u, u);
            
            ll current_val_u = 0;
            int p = hld.hld.dep[u] & 1;
            FOR(i, 0, LOG-1) if(u_to_root.bit_num[p][i]) current_val_u |= (1LL << i);

            // 2. 构造修正 Tag
            Tag need_apply(current_val_u, current_val_u);
            
            // 3. 查子树信息
            // 【关键修正】：这里必须查 SubtreeNode (包含 u)，因为题目求的是子树内"节点对"的美观度
            // 如果查 SubtreeEdge (排除 u)，就会漏掉所有涉及 u 的点对，导致答案变小。
            Info res = hld.querySubtreeNode(u);
            
            // 4. 应用修正
            res.apply(need_apply);
            
            ll ans = 0;
            ll total = res.cnt[0] + res.cnt[1];
            FOR(i, 0, LOG-1) {
                ll ones = res.bit_num[0][i] + res.bit_num[1][i];
                ans += (ones * (total - ones)) * (1ll << i);
            }
            cout << ans << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll lT; cin >> lT;
    while(lT--) Solve();
    return 0;
}

心路历程（WA，TLE，MLE……）