aδδitivee [yukicoder 900]

https://yukicoder.me/problems/no/900

前提知識

• HL分解
• 遅延評価セグメントツリー(区間add,区間sum)

解説

https://yukicoder.me/submissions/387106

クエリを見ると部分木クエリとパスクエリになっている。
木に対して部分木もパスも行けるHL分解という手法がある。
HL分解を使って、部分木の全ての重みにxを加算し、パスの重みの総和を計算しよう。
辺にコストがあると扱いにくいので頂点に落としておくのがおすすめ。
辺のコストを端点の深さが深い方の頂点にうつしておく。
すると、部分木での操作は、部分木全体に+xして、部分木の根だけ-xすると辺に加算することになる。

HL分解を使えば、部分木もパスも区間に変換して考えることができる。
よって、区間に対してx加算と総和取得ができればいい。
これは遅延評価セグメントツリーを使えば実現できる。

ライブラリで殴っている感があるが、ライブラリで殴れる場合は殴っとこう。

//---------------------------------------------------------------------------------------------------

int N, U[101010], V[101010], W[101010];
LazySegTree<ll, 1 << 17> st;
ll ans;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    HLDecomposition hld(N);
    rep(i, 0, N - 1) {
        cin >> U[i] >> V[i] >> W[i];
        hld.add(U[i], V[i]);
    }
    hld.build();

    rep(i, 0, N - 1) {
        int v = U[i];
        if (hld.depth[v] < hld.depth[V[i]]) v = V[i];
        st.update(hld.vid[v], hld.vid[v] + 1, W[i]);
    }

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int a, x;
            cin >> a >> x;
            st.update(hld.in[a], hld.out[a], x);
            st.update(hld.vid[a], hld.vid[a] + 1, -x);
        }
        else
        {
            int b;
            cin >> b;

            ans = 0;
            hld.foreach(0, b, [](int x, int y) {
                ans += st.get(x, y + 1);
            });
            printf("%lld\n", ans);
        }
    }
}