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になっている
のどちらかになっていれば、すべての石を取り除くことができる。
反省
- 根付き木で考える
- 葉ノードから決定的に決まるものを見つける