2020年8月17日月曜日

CodeChef August Challenge 2020 - Chefina and Strange Tree

与えられたグラフを根付き森とみなすと、ある頂点vvを消す操作は、vvのそれぞれの子の部分木とvvの親側の木とをすべて切り離す操作と考えられる。オイラーツアー(pre-order)上で考えると、部分木は連続した区間に対応しているので、区間を切り貼りすることができればよい（下図）。そこでオイラーツアーを平衡二分木で保持することにする。

chefcomp

平衡二分木にmin⁡\minを載せて、さらに遅延更新で加算ができるようにする。町PiP_iについての処理の流れは次のようになる:

  1. PiP_iを含む木TT（=1つの平衡二分木で表されたオイラーツアー）のすべての頂点の値からAPiA_{P_i}を引く。
  2. TTのmin⁡\minを求めて、00以下ならTT上の二分探索で最小値を取る頂点vvを探す。vvがii日目に00になったと記録し、vvの値を+∞+\inftyにセットする（再び00にならないようにするため。） min⁡\minが00より大きくなるまでこれを繰り返す。
  3. 上図のようにPiP_iの隣接頂点に関する部分木をすべて切り離す。

1を行う際に、PiP_iを含む平衡二分木を得る必要があるが、永続UnionFindを使った。事前に列(Pi)(P_i)を逆順に走査しながら頂点をつないでおく。PiP_iを（正順に）処理する際には、その時点でのPiP_iに対応する（UnionFind上の）根に平衡二分木を持たせるようにした。（でも、ちゃんと前処理すれば普通のUnionFindでできるか。）

計算量は全体でO(Nlog⁡N){O}(N\log N)。

明らかに過剰なデータ構造をごちゃごちゃと貼ってしまった。physics0523さんの解説によると、操作の構造自体が木になっていることを利用できるらしい。なるほど……

投稿者