Educational DP Contest / DP まとめコンテスト V - Subtree
解法
全方位木dpをします。
初めに頂点1が根である際の値を求めます。
を根とする部分木について、を黒で塗った際の部分木の塗り方
とすると、頂点の子の集合をとして、
となります。
を根とした際の求めるべき答え
とすると、
となります。
が求まっている際に、その子であるについての答えを求めるため、へシフトすることを考えます。
書き換えるべき場所は、とのみになります。
については、定義に基づいて計算すればよいので、を求めることのみ考えます。
となるので、あとはこれを計算すればよいのですが、愚直に計算をすると間に合いません。
ある数列について、を高速に計算する方法を考えます。
これは、累積和同様に数列の前方からの累積積と、後方からの累積積をあらかじめ計算しておくと、それぞれの累積積について、番目の手前の値をかけ合わせることで、前計算のみで、で計算することができます。
あとは、これを利用することで、dfsを行いつつ、根の付け替えを行い答えを求めることができます。
感想
全方位木の概要は知っていたので考察はすんなり進んだのですが、累積積を利用する部分を思いつくのが難しかったです…