ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト V - Subtree

問題
提出コード

解法

全方位木dpをします。
初めに頂点1が根である際の値を求めます。
dp_{j}[i] = jを根とする部分木について、iを黒で塗った際の部分木の塗り方
とすると、頂点iの子の集合をS_{i}として、
\displaystyle dp_{j}[i] = \prod_{p \in S_{i}}(dp_{j}[p] + 1)
となります。
ans[i] = iを根とした際の求めるべき答え
とすると、
\displaystyle ans[1] = \prod_{p \in S_{1}}(dp_{1}[p] + 1)
となります。
dp_{i}が求まっている際に、その子であるjについての答えans[j]を求めるため、dp_{j}へシフトすることを考えます。
書き換えるべき場所は、dp_{j}[i]dp_{j}[j]のみになります。
dp_{j}[j]については、定義に基づいて計算すればよいので、dp_{j}[i]を求めることのみ考えます。
\displaystyle dp_{j}[i] = \prod_{p \in S_{i},p \neq j}(dp_{i}[p] + 1)
となるので、あとはこれを計算すればよいのですが、愚直に計算をすると間に合いません。
ある数列a_1, a_2, a_3, ... a_nについて、\frac{\prod_{k=1}^{n}a_k}{a_i}を高速に計算する方法を考えます。
これは、累積和同様に数列の前方からの累積積と、後方からの累積積をあらかじめ計算しておくと、それぞれの累積積について、i番目の手前の値をかけ合わせることで、前計算O(N)のみで、O(1)で計算することができます。
あとは、これを利用することで、dfsを行いつつ、根の付け替えを行い答えを求めることができます。

感想

全方位木の概要は知っていたので考察はすんなり進んだのですが、累積積を利用する部分を思いつくのが難しかったです…