2019年5月17日金曜日

TDPC N - 木

TDPC N - 木

各辺e:={u,v}Ee := \{u, v\} \in Eについて、eeを最初に描く場合の数を求めて足し合わせるという方針で解きたい。uuのほうにある部分木とvvのほうにある部分木を描く場合の数がわかれば、eeを最初に描く場合の数もわかりそう。この方針で定式化してみる:

uuを親と見たときの)vvを根とする部分木に辺{u,v}\{u, v\}を追加した木Tu,vT_{u, v}とする。Tu,vT_{u, v}の辺の数をTu,v|T_{u, v}|とし、{u,v}\{u, v\}から描き始める場合のTu,vT_{u, v}の描き方の総数をf(u,v)f(u, v)とする。

f(u,v)f(u, v)の漸化式を与える。頂点vvの子をw1,w2,...,wkw_1, w_2, ..., w_kとするとき、

f(u,v)=(Tv,w1+...+Tv,wk)!Tv,w1!...Tv,wk!f(u,w1)...f(u,wk)f(u, v) = \frac{(|T_{v, w_1}| + ... + |T_{v, w_k}|)!}{|T_{v, w_1}|!...|T_{v, w_k}|!}f(u, w_1) ... f(u, w_k)

となる。左から掛けているのは多項係数である。(vvを根とする部分木を描くのに合計Tv,w1+...+Tv,wk|T_{v, w_1}| + ... + |T_{v, w_k}|本の辺を描く必要があり、描いている途中のどの時点でも常にw1,w2,...,wkw_1, w_2, ..., w_kを根とする部分木のどれを伸ばすか任意に選べるため。) vvが子を持たない場合はf(u,v)=1f(u, v) = 1である。

ffがわかれば辺{a,b}E\{a, b\} \in Eを最初に書いた時の残りのn2n-2本の辺の描き方の総数が求まり、それらを足し合わせれば答えになる:

(a,b)E(n2)!(Ta,b1)!(Tb,a1)!f(a,b)f(b,a)\sum_{(a, b) \in E} \frac{(n-2)!}{(|T_{a, b}| - 1)!(|T_{b, a}| - 1)!}f(a, b)f(b,a)

これも上と考え方は同じである。

計算方法について。Tu,v|T_{u,v}|vvを根とする部分木の頂点の数に等しいので、DFSしながらメモすればよい。f(u,v)f(u, v)もまったく同じで、DFSしながらメモするだけである。

計算量について。メモ化すれば1回ずつDFSするだけ1になるので、O(n){\mathcal O}(n)に見える……のだが、なんとなく信じられなくて2×1052 \times 10^5の木を作って実験してしまった。これがO(n){\mathcal O}(n)で求まるのか。 スターの時にO(n2)回見ることになるので、線形ではなかった。線形にするには全方位木DPをする必要がある。


  1. 常に辺を双方向に調べているので2回というべきかも。 ↩︎