perogram

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を読んでください。それでも分からなければ続きを読んでください

補足

f:id:peroon:20191123181602p:plain

  • 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]なのでセグ木がどこも更新しなくなってしまう