Codeforces 276E(樹狀數組)

題意：一棵樹有n個節點，1是根節點，根節點的子節點是單鏈，然後現在有兩種操作0 v x d表示距離節點v為d的節點權值都加x，操作1 v問v節點的權值，初始節點權值都是0。
題解：看了別人的題解才會的，維護兩種樹，把每條單鏈都當做一個樹狀數組維護當前鏈上每個節點的權值，另一種是從根節點開始維護距離為x的節點的權值。

#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N = 100005;
int n, q, dis[N], root[N];//數組存深度和單鏈頭節點
vector g[N];
vector > C;

int lowbit(int x) {
    return x & (-x);
}
//對於根節點的樹，en代表距離根節點的長度，如果等於0就不加，因為變量sum加過了
//對於單鏈的樹，st到en向下延伸
void Add(int st, int en, int val, int cur) {
    if (st > en)
        return;
    int sz = C[cur].size();
    for (int i = st; i < sz; i += lowbit(i))
        C[cur][i] += val;
    for (int i = en + 1; i < sz; i += lowbit(i))
        C[cur][i] -= val;
}

ll Sum(int deep, int cur) {
    ll ret = 0;
    int sz = C[cur].size();
    for (int i = deep; i > 0; i -= lowbit(i))
        ret += C[cur][i];
    return ret;
}

void dfs(int u, int pre, int cnt, int cur) {
    dis[u] = cnt;
    root[u] = cur;
    C[cur].push_back(0);
    int sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (v != pre)
            dfs(v, u, cnt + 1, cur);
    }
}

int main() {
    scanf(%d%d, &n, &q);
    for (int i = 0; i <= n; i++)
        g[i].clear();
    int a, b, op, l, r, x, v, d;
    for (int i = 1; i < n; i++) {
        scanf(%d%d, &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int sz = g[1].size();
    C.resize(sz + 5);
    for (int i = 0; i < sz; i++) {
        C[i + 1].push_back(0);//根節點
        dfs(g[1][i], 1, 1, i + 1);
    }
    C[0].resize(N, 0);
    ll sum = 0;//根節點1的權值
    while (q--) {
        scanf(%d, &op);
        if (op == 0) {
            scanf(%d%d%d, &v, &x, &d);
            int cur = root[v];      
            if (d < dis[v])//不會延伸到其他鏈
                Add(dis[v] - d, dis[v] + d, x, cur);
            else {
                sum += x;
                Add(1, dis[v] + d, x, cur);//單鏈的子節點延伸
                Add(1, d - dis[v], x, 0);//向根節點延伸
                Add(1, d - dis[v], -x, cur);//重復加的減掉
            }
        }
        else {
            scanf(%d, &v);
            if (v == 1)
                printf(%lld
, sum);
            else {
                int cur = root[v];
                printf(%lld
, Sum(dis[v], cur) + Sum(dis[v], 0));//向根節點延伸的單鏈上的和加上根節點向下延伸的加上的權值
            }
        }
    }
    return 0;
}