Starters 212-Beautiful Sum · znzryb
## 思路讲解
<!-- Notion block type: synced_block -->
## AC代码
[https://www.codechef.com/viewsolution/1209777968](https://www.codechef.com/viewsolution/1209777968)
::: 源代码
```cpp
// 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……）