与えられたグラフを根付き森とみなすと、ある頂点$v$を消す操作は、$v$のそれぞれの子の部分木と$v$の親側の木とをすべて切り離す操作と考えられる。オイラーツアー(pre-order)上で考えると、部分木は連続した区間に対応しているので、区間を切り貼りすることができればよい（下図）。そこでオイラーツアーを平衡二分木で保持することにする。
平衡二分木に$\min$を載せて、さらに遅延更新で加算ができるようにする。町$P_i$についての処理の流れは次のようになる:
- $P_i$を含む木$T$（=1つの平衡二分木で表されたオイラーツアー）のすべての頂点の値から$A_{P_i}$を引く。
- $T$の$\min$を求めて、$0$以下なら$T$上の二分探索で最小値を取る頂点$v$を探す。$v$が$i$日目に$0$になったと記録し、$v$の値を$+\infty$にセットする（再び$0$にならないようにするため。） $\min$が$0$より大きくなるまでこれを繰り返す。
- 上図のように$P_i$の隣接頂点に関する部分木をすべて切り離す。
1を行う際に、$P_i$を含む平衡二分木を得る必要があるが、永続UnionFindを使った。事前に列$(P_i)$を逆順に走査しながら頂点をつないでおく。$P_i$を（正順に）処理する際には、その時点での$P_i$に対応する（UnionFind上の）根に平衡二分木を持たせるようにした。（でも、ちゃんと前処理すれば普通のUnionFindでできるか。）
計算量は全体で${O}(N\log N)$。
明らかに過剰なデータ構造をごちゃごちゃと貼ってしまった。physics0523さんの解説によると、操作の構造自体が木になっていることを利用できるらしい。なるほど……
