C - On Changing Tree ～オイラーツアーとセグ木～

Quiz

https://codeforces.com/contest/396/problem/C

N頂点の木 (3 x 10^5)
クエリQ (3 x 10^5)
・1 v x k : 頂点vにxを足す。vの子孫にも、vからの距離 i によりx - i kを足す
・2 v : 頂点vの値をmod 10^9+7でprint

• 足す値が一律ではないことをどう扱うか

AC

https://codeforces.com/contest/396/submission/65574597

解法

• まずは「npca2015年部誌_木に対する一般的なテク達.pdf」p34を読んでください。それでも分からなければ続きを読んでください

補足

• p34を読んでも私は最初理解できなかったのでそこを補足します
• たとえば上の画像のようなサンプルを考えます
• v以下に同じ値を加算するのは、オイラーツアー＋セグメントツリーで可能
• 今回の解法では、まずv以下の子孫にxではなくx+k * depth[v]を足す
• すると、v以下の子孫全てに足しすぎ状態になってしまう

* ノード2の場合、x   を足したいのにx+2kを足したので、2kの余分
* ノード3の場合、x- kを足したいのにx+2kを足したので、3kの余分
* ノード4の場合、x-2kを足したいのにx+2kを足したので、4kの余分

* ★2k, 3k, 4kこの係数 2, 3, 4は木の深さになっている！

• 木の深さは事前計算できる
• 余分な分はQuery2が来た時に借金返済してから答えることにする
• 借金情報は、専用のセグ木で管理する。p34でいうover
• ノード2,3,4,5,6に共通にkを足すことで借金登録ができる。実際の借金額はk * depth[node_id]で求まる
• 以上、補足できていれば幸いです

おまけ

• オイラーツアーで雑にセグ木に範囲加算していると葉っぱでバグる
• この部分

        // v以下にx+depth*kを加算
        ll val = x + depth[v]*k; val %= mod;
        sum.update(tour.L[v], tour.R[v]+1, val);
        // v以下に後で返済するKを記録
        over.update(tour.L[v], tour.R[v]+1, k);

• 最初は下記のようにしていた

        // v以下にx+depth*kを加算
        ll val = x + depth[v]*k; val %= mod;
        sum.update(tour.L[v], tour.R[v], val); // NG
        // v以下に後で返済するKを記録
        over.update(tour.L[v], tour.R[v], k); // NG

• この書き方だと、vが葉の時、tour.L[v] == tour.R[v]なのでセグ木がどこも更新しなくなってしまう

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～