DP V

木が与えられる、どの黒頂点から黒頂点へも黒頂点だけを通って到達できるような塗り分けの総数を求める問題

部分木の個数を求めるって理解でいいのかな？

あ「頂点vが黒であるような組み合わせは何通りか」を答えるのか。単純に部分木を求めるのではオーダーがN倍になっちゃうから部分問題を使いまわしたいわけね

素朴に作って問題が大きいところだけRE

タプルをキーにした辞書が遅かろうと思って積の整数をインデックスにしてた

Nが10^5まで行くので2乗で10^10になってMemoryError

手元ではメモリがたくさんあるので動いてしまう

MLEではなくREになるので原因がわかりにくかった

1つの頂点から生えている辺が多い時に集計がO(N)になってしまう

「たくさんの中から1つ取り除いたものの集計」を演算結果を使い回して計算量削減する必要がある

乗算での集計は0に逆元がないので「全部かけたものから一つだけ戻す」ができない、加算なら逆元があるからできるのだが…。

というわけで前からと後ろからの累積積を作る

これって位数制限のないグラフだと常に必要になると思う

code:python

N = 700

xs = range(1, N + 1)

cur = 1

for i in range(N):

cur = 1

for i in range(N - 1, -1, -1):

# print(head)

# print(tail)

# print(one_out_product)

if not"TEST":

for i in range(N):

for j in range(N):

if i == j:

continue

assert bluteforce == one_out_product

作ったはいいが、これの実行タイミングは？

他の人のコードを読む

Python 523msec

なるほど、僕のコードは「全部白、根が黒い、それ以外で根が白い」の3つにわけて後者二つを伝搬してるけど、子供の根が白いと親が黒になり得ないので最終計算の時に必ず無視されるから伝搬する必要がないのか

「子供の値を掛け合わせて1を足したもの」という更新で良い

1を足すのは子供が全白のパターン

しかも再帰呼び出しは必要ない、と。最初に幅優先探索でたどった順番を記録している。またその時に逆向きの辺を消している。

https://gyazo.com/b910e1af8eb9355d9717ec6f26604f7f

code:python

def solve(N, M, edges):

# convert bidirectional graph to tree

root = 1

bfs_visited_order = []

while to_visit:

cur = to_visit.popleft()

bfs_visited_order.append(cur)

continue

to_visit.append(child)

# default: if no child, one black, one white (1 + 1)

# f(x) = prod(f(c) for c in children) + 1

# stores multiply result (1 is unity)

# visit vertexes except root, in reversed order

# root: multiply children and don't add one

# the one is "all-white" pattern

for cur in bfs_visited_order:

prod = 1

prod %= M

# multiply right-to-left accumlated products

prod = 1

prod %= M

# update final result