DPまとめコンテスト/V - Subtree - 競技プログラミング用 知識集積所【7/25更新】

---

問題

DP-V

必要知識

ABCのB以下レベルの内容は省略

• 全方位木DP（未作成）
  • 動的計画法
  • 深さ優先探索（未作成）または幅優先探索（未作成）
  • 累積和の積バージョン
  • 隣接行列（未作成）
• 剰余類環

考え方

各頂点のそれぞれの方向の部分木について、黒が分断しないように色を塗る方法を求める。
具体的には、先端側から順番に白く塗るパターン数を求める。
条件を考えれば、あとはそれらの積をとれば、答えである。

問題は、それらの値を全頂点分、どうやって高速に求めるか。
そこに、いわゆる全方位木DPを用いる。
（挿入される表は、入力例1での様子）

まず、1つ根を決め、深さ優先探索（未作成）または幅優先探索（未作成）で根から近い順に頂点を並べる。
（厳密には、全ての辺について、根側の頂点が先に出てくるように並べる）

根 1→2→3 葉

根	辺	頂点	辺	葉
頂点1	?←→?	頂点2	?←→?	頂点3

次に、それを後ろから順に、根がある方向以外の部分木を黒が分断しないように色を塗る方法の数をもらうDPで求める。
これは、根がある方向以外の塗り方を全て掛け算して（葉なら1）、最後に1を足せばよい（全部白の分）。

根	辺	頂点	辺	葉
頂点1	?←→?	頂点2	?←→2	頂点3

根	辺	頂点	辺	葉
頂点1	?←→3	頂点2	?←→2	頂点3

終わったら、今度は根っこ側から順に、全方向の部分木の塗り方を配るDPで求める。
各方向について、「自身の方向以外の全部の方向の値を掛けて1足す」をやればいい。
ただし、これを愚直にやると、1つの頂点に針山のように頂点がくっついていると計算量がO(隣接数^2)なのでTLEする。
どうにか1つの頂点での処理をO(隣接数)で求めなければならない。

もしmが素数であれば全部かけてから自身方向の値で割り算（剰余類環参照）することができる。
しかし、今回はmが合成数かもしれないし積がmの倍数かもしれないので、その方法は使えない。
そのため、累積和の積バージョンを用いる。
左からの累積積と右からの累積積を求めておけば、自分以外の塗り方の積はすぐに出せる。

根	辺	頂点	辺	葉
頂点1	2←→3	頂点2	?←→2	頂点3

根	辺	頂点	辺	葉
頂点1	2←→3	頂点2	3←→2	頂点3

ついでに全方向の積（1を足さない）も出せば、それがその頂点での答えである。

答えはmod mでの値なので、剰余類環も参照。

解答例

解答例

注意点

別解