読者です 読者をやめる 読者になる 読者になる

phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC010 C. Cleaning

問題

Nノードからなる木が与えらえる。
各ノードにはA[i]個の石が置かれている。
「2つの(異なる)葉ノードを選び、そのパス上のノードすべてから1つずつ取り除く」という操作を繰り返して、すべての石を取り除けるか答えよ。
ただし、パス上に石のないノードがある場合は操作は行えない。

制約

2 <= N <= 10^5
0 <= A[i] <= 10^9

解説

https://atcoder.jp/img/agc010/editorial.pdf

適当にノードを選んで根にして、根付き木として考える。
あるノードvについて、親ノードがw、子ノードがc_1,c_2,...,c_kであるような場合を考える。

vとc_iの間の辺が何回パスとして通過するかをp[c_i]とすると、vとwの間の辺が何回パスとして通過するかp[w]は、ノードvの通過回数A[v]が決まっているので、
p[w] = 2*A[v] - Σp[c_i]
でなければならない。
このとき、条件として、

  • p[w]は0以上A[v]以下の数でなければいけない
  • もし、子ノードが1つの場合は、p[w]=A[v]=p[c_1]でなければならない
  • vの周りの各辺の通過回数p[x]は、辺の通過回数合計/2回 = (p[w]+p[c_1]+...+p[c_k])/2以下でなけれなならない

を満たす必要がある。

これを再帰的に繰り返し(dfs)、根まで求め、

  • 根が葉ノードの場合、根の疑似的な親ノードへの辺の通過回数=A[root]になっている
  • 根が葉ノードでない場合、根の疑似的な親ノードへの辺の通過回数=0になっている

のどちらかになっていれば、すべての石を取り除くことができる。

反省

  • 根付き木で考える
  • 葉ノードから決定的に決まるものを見つける