yukicoder No.1302 Random Tree Score O(N+logp)
プリューファーコードというものを考えまふ.
木の各頂点の次数は, 対応するプリューファーコードにその頂点番号が現れる回数+1に等しいれふ.
プリューファーコードを次数列に対応させる試みとして, 次のような操作を考えまふ.
個の箱の中に白玉が1個ずつ入ってる状態から, 次の操作を 回行う.
- 箱を一つ選び, 白玉を1個入れる.
(箱同士・玉同士を区別することに注意)
すると, 次数の総積は次の値に一致しまふ.
- 各箱から白玉を1個ずつ選び, 黒玉に取り換える方法の通り数
全ての次数列に対してこの値を求めるには, 次のような操作の通り数を考えれば良いれふ.
個の箱の中に白玉が1個ずつ入ってる状態から, 次の操作を 回行う.
- 箱を一つ選び, 白玉を1個入れる. または, まだ黒玉が入って無い箱を一つ選び, 黒玉を入れる.
操作後, まだ黒玉が入って無い箱すべてに対し, 最初から入ってた白玉を黒玉に取り換える.
に対し, 回の操作のうち黒玉を 回入れる方法は, 次のものを掛け合わせた数れふ.
- 回の操作から 回を選ぶ通り数
- 個の箱から黒玉を入れる箱を重複なく選ぶ通り数
- 個の箱から白玉を入れる箱を重複を許して選ぶ通り数
適切に前計算をすれば になりまふ.