AtCoder ABC152 F - Tree and Constraints

次のようなDPを定義する。

dp[i][j] := 通り数

あらかじめ、「ある辺を黒で塗ったときにどの制約を満たすか」を求めておく。その上で、根付き木上でDPを行う。木DPなので2種類の遷移を定義する必要がある。辺の持ち上げ操作とマージ操作。それぞれの遷移は次のようになる。

木DPでの親をu、子をv、それらを結ぶ辺をeとする。そして、辺xを黒く塗ったときに満たす制約の集合をC(x)とすると、遷移は次のようになる。

tdpのtはtempの略で、一時的なdp配列を表す。初期値はすべて0とする。

この遷移をjの状態数だけ行う。

マージ対象のdp配列の一方をldp、もう一方をrdpとすると、次のようになる。

これを素直に実装すると計算量O(2^2M)になるが、アダマール変換を使うことでO(M2^M)に落とせる。

アダマール変換の実装は以下のページからお借りしました。

この問題を解く際に色々なことを考えた。

木DPには遷移が2種類あるので、それぞれ別に考える（一緒に考えると頭の中がオーバーフローする）
持ち上げ操作は+、マージ操作は*のようなもの
各操作の単位元をどうするかについてきちんと考えると実装が楽になる（単位元を考えないとif文がひとつ増える。単位元を雑に考えるとバグる）
FFTさえ理解できれば、畳み込みのときに使われる様々な変換（メビウス変換、ゼータ変換、アダマール変換）がすぐに理解できるかもしれない。少なくとも、アダマール変換はすぐに使えた
木のパス上の頂点はO(N)で列挙できる

想定解は包除原理とのこと。「補集合を数え上げる」という典型を完全に忘れていた。実際に実装すると物凄く楽だった。こちらの解法を思いつきたかった気もする。けれど、木DPとアダマール変換について学べたので良しとする。

ぺんぎんメモ