TDPC N - 木

• 問題
• AC

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

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

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

$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)$

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

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

$\sum_{(a, b) \in E} \frac{(n-2)!}{(|T_{a, b}| - 1)!(|T_{b, a}| - 1)!}f(a, b)f(b,a)$

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

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

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

---

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