Ki [AtCoder Beginner Contest 138 D]

https://atcoder.jp/contests/abc138/tasks/abc138_d

前提知識

• imos法

解説

https://atcoder.jp/contests/abc138/submissions/7014727

木上でimos法をやる。
頂点p[j]にx[j]を足す。この状態で根からある頂点の値を子供に足していく。
これを続けていくと、部分木すべてに+x[j]を伝搬させることができる。
期限がないので、一般のimos法のように終点に-x[j]をする必要はない。

int N, Q;
vector<int> E[201010];
int val[201010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int pa = -1) {
    fore(to, E[cu]) if(pa != to) {
        val[to] += val[cu];
        dfs(to, cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    rep(q, 0, Q) {
        int p, x; cin >> p >> x;
        p--;
        val[p] += x;
    }

    dfs(0);

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", val[i]);
    }
    printf("\n");
}