Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【yukicoder No.900 aδδitivee】オイラーツアー:木を一直線にする

実装が難しくてしてませんが、考え方だけは理解したので書いておきます。

No.900 aδδitivee - yukicoder

問題

木が与えられる。以下2種類のクエリを処理せよ

  1. a(v): v以下のエッジに重みxを追加する
  2. q(v): 0からvまでの重みの総和を求めよ

初期値はどうでもいいので、更新された差だけを求めることにします。初期値分は最初にDFSで計算して後で足せばよいでしょう。

方針

深いノードほど総和の影響は大きいということがわかります。なんとかして、「木をうまいこと1次元にして、深いやつほど和がたくさんになるように遅延セグツリーしたい」というのは直感的にわかります。

そのやり方は、

f:id:akiradeveloper529:20191006143047j:plain

  1. 行きがけ帰りがけでオイラーツアーをする
  2. こうすると、あるノードの深さは、そこまでにある有向辺の、下方向-上方向の差分ということがわかる
  3. 下方向のエッジで到達した時に+1, 上方向で-1と記録しておく
  4. こうすると、重みのある遅延セグツリーと見ることが出来る

通常の範囲加算というのは、符号がなく全部+1ということです。

何がポイントかというと、

  1. オイラーツアーをしたことによって、あるノード以下のノードを一直線にすることが出来ている
  2. 行きがけ帰りがけを記録することによって、符号を相殺することが出来ている

です。

あとはこれを遅延セグツリーに落とし込むだけですが、そのためには、各マスに重みをつけることが出来るように設計する必要があります。私のライブラリもそうですし、通常はそうなってないでしょう。気が向いたら実装しておきます。