当初の方針
- DPだろうなあ・・・(定義が分かるとは言っていない2回目)
- 木だから、木の嬉しい性質を利用するのかな
- まず全探索。白か黒で遷移してチェック。これは2^10^5なのでダメ
- 両端が黒になるものを列挙して、残りの組み合わせを足していくのは?
- 重複がある。それを除く方法も分からない(たぶんない)
- 諦めて解説を見る
解説を読んで
木DPというらしい。DP好きとしてはマスターしておきたいところ。
解説の通りに実装したらACしそうだけど、なぜそのように立式できるか
分からない。
サンプルケース1でテストしてみる。
やべえなんだこれ天才か
いざ実装
DPって書いてあるけど、木だからループはないし、
根から探索するので大丈夫でしょう → 大嘘
debugを見てみると同じ探索をしている。フィボナッチ数列みたいな感じ。
メモ化再帰で解いてみる → TLE
Submission #924250 - AtCoder Beginner Contest 036 | AtCoder
やっぱりDPしないとダメなので、PriorityQueueに突っ込んで
深さの大きいところから計算しておく。
こうすれば前に書いたメモ化再帰もDPっぽい動きをしてくれる。
(今思えばソートで十分なのだけれど、イメージとして
PriorityQueueのほうがしっくりきた)
AC。
ちょっと待てよ?
なんでメモ化再帰しているのにTLEするのだろう。
考えられること
- 関数呼び出しのオーバーヘッドがかかる
(木に対してDFSするとよくあることで
最悪スタック領域が足りなくなりREになる)
- debug文を残していたのが悪かった。
debug文を消して提出してみる。 → AC
Submission #924303 - AtCoder Beginner Contest 036 | AtCoder
まじかい。しかもlog(N)がない分だけか、早くなってる。
次からは消してから提出しよう・・・。