Codeforces 276E：樹上操作與樹狀數組維護

問題描述

給定一棵以 1 為根的樹，根的每個孩子形成一條單鏈（即樹退化為「星形+鏈」）。兩種操作：

1. 0 v x d：距離節點 v 為 d 的所有節點權值 +x。
2. 1 v：查詢節點 v 的權值。

初始權值均為 0。n, q ≤ 10⁵。

核心觀察

樹結構特殊：根 1 的每個子樹是一條鏈。任意節點 v 到距離 d 的節點集合分佈在：
(1) v 所在鏈上向上/向下 d 範圍；
(2) 經過根 1 到達其他鏈上深度 ≤ d−dist(v,1) 的節點。

雙樹狀數組維護

• 鏈內 BIT：每條鏈建一個 BIT，下標為深度，支援區間加、單點查。
• 根向 BIT：一個全局 BIT，下標為深度，維護從根向下傳播的增量。

操作拆解

// 區間 [l, r] 加 val，BIT 下標從 1 開始
void addBIT(vector<long long> &bit, int l, int r, long long val) {
    for (int i = l; i < (int)bit.size(); i += i & -i) bit[i] += val;
    for (int i = r + 1; i < (int)bit.size(); i += i & -i) bit[i] -= val;
}
long long queryBIT(const vector<long long> &bit, int idx) {
    long long res = 0;
    for (int i = idx; i > 0; i -= i & -i) res += bit[i];
    return res;
}

處理操作 0 v x d

int chain = root[v]; // v 所在鏈編號
int dep = depth[v];  // v 在鏈內深度（根為 1）
if (d < dep) { // 不波及根
    addBIT(bit[chain], dep - d, dep + d, x);
} else { // 波及根及其他鏈
    rootVal += x; // 根節點自身
    // 當前鏈：深度 1 到 dep+d
    addBIT(bit[chain], 1, dep + d, x);
    // 根向全局：深度 1 到 d-dep
    addBIT(bit[0], 1, d - dep, x);
    // 扣除當前鏈在根向 BIT 中被重複加的部分
    addBIT(bit[chain], 1, d - dep, -x);
}

查詢操作 1 v

if (v == 1) return rootVal;
int chain = root[v], dep = depth[v];
return queryBIT(bit[chain], dep) + queryBIT(bit[0], dep);

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> g[MAXN];
int depth[MAXN], rootChain[MAXN];
vector<vector<long long>> bit;
long long rootVal = 0;

void dfs(int u, int p, int dep, int chain) {
    depth[u] = dep; rootChain[u] = chain;
    bit[chain].push_back(0); // 佔位，使下標從 1 開始
    for (int v : g[u]) if (v != p)
        dfs(v, u, dep + 1, chain);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q; cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        g[a].push_back(b); g[b].push_back(a);
    }
    int chains = g[1].size();
    bit.assign(chains + 1, vector<long long>(1, 0)); // bit[0] 為根向
    bit[0].assign(MAXN, 0);
    for (int i = 0; i < chains; ++i)
        dfs(g[1][i], 1, 1, i + 1);
    while (q--) {
        int op; cin >> op;
        if (op == 0) {
            int v, x, d; cin >> v >> x >> d;
            int ch = rootChain[v], dep = depth[v];
            if (d < dep) {
                addBIT(bit[ch], dep - d, dep + d, x);
            } else {
                rootVal += x;
                addBIT(bit[ch], 1, dep + d, x);
                addBIT(bit[0], 1, d - dep, x);
                addBIT(bit[ch], 1, d - dep, -x);
            }
        } else {
            int v; cin >> v;
            if (v == 1) cout << rootVal << '\n';
            else {
                int ch = rootChain[v], dep = depth[v];
                cout << queryBIT(bit[ch], dep) + queryBIT(bit[0], dep) << '\n';
            }
        }
    }
    return 0;
}

複雜度

預處理 O(n)，每操作 O(log n)，空間 O(n)。