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