AtCoder Beginner Contest 160

　Eまでは結構順調だったのに、一時間以上かけてFが解けず。全方位木DPだということは分かっていたのですが。

コンテストへのリンク
コンテスト後のツイート

F - Distributing Integers

　部分木のノード数と、答えをもって全方位木DP（rerooting）。
　この問題でも全方位木DPの実装にかなりの時間を取られている。

　コンテスト中TLEしてしまったのは、全方位木DPをしようとしているのに、前計算を利用できていないところがあり、二乗の計算量になってしまったためでした。
　これに気付けないのはまずい。


　復習のためと思ってもう一度書き直してみたのだけど、やはりかなり時間がかかってしまった上、また二乗で提出して一回TLEしてしまった……。

　全方位木DPは辺に関するDPとして理解している（一回目は葉から根の方向に、二回目は根から葉の方向に値を決める）のだけど、DPテーブルとしてはDP[node]=valueとするため、一回目と二回目で見る部分が違ってしまうのが混乱のもとだと思う。
　（一回目では、DP[x]でnode x→P[x]の辺に関する値を求めるため、xの子供たちを見れば良いけど、二回目では、DP[x]でnode P[x]→xの辺に関する値を求めるので、P[x]に繋がる辺たちを調べることになる。それが紛らわしい）

　これでいつも戸惑ってしまうのだけど、どうにかできないだろうか……。ちゃんとライブラリ化しなくちゃいけないのかな。