F - Maximum Diameter Editorial by ngtkana
Prüfer sequence への言い換え
実を言うとこの言い換えは本質的には必要なく、次数列のままでも同じ議論ができるのですが、わかりやすさのために Prüfer sequence に言い換えてからお話させていただきます。
\(2\) つのラベル付き木の次数列が等しいことは、Prüfer sequenceにおける各頂点の登場回数が等しいことと同値です。またその直径の最大は Prüfer sequence に登場する頂点の種類数 + \(1\) に等しいです。
そこで \(\left \lbrace 1, \dots, N \right \rbrace\) のソート済み \(N - 2\) 項列 \(P _ 1, \dots, P _ { N - 2 }\) の集合を \(\mathcal P\) とおき、各 \(P \in \mathcal P\) に対してそのスコア \(f(P)\) を、\(P\) に登場する頂点の種類数 + \(1\) と定義すると、答えは
\[ \mathtt{ans} = \sum _ { P \in \mathcal P } f ( P ) = \left \lvert \mathcal P \right \rvert \cdot E \left \lbrack f \right \rbrack \]
(ただし \(E \left \lbrack f \right \rbrack\) は\(\mathcal P\) の要素数と\(P\) を \(\mathcal P\) から一様ランダムに選択したときの \(f ( P )\) の期待値)となります。
要素数 \( \left \lvert \mathcal P \right \rvert \)、期待値 \( E \left \lbrack f \right \rbrack\) の計算
\(\mathcal P\) の要素は Stars and bars (combinatorics) - Wikipedia にある方法により、\(N - 2\) 個の ★ と \(N - 1\) 個の | から成る長さ \(2 N - 3\) の文字列 \(s\) と一対一対応します。この言い換えをすると、
\[ \begin{aligned} \left \lvert \mathcal P \right \rvert &= \binom { 2 N - 3 } { N - 1 } \\ f ( P ) &= N - 1 - (s の ★★ に等しい部分文字列の個数) \end{aligned} \]
がわかります。 さらに \(s\) の長さ \(2\) の部分文字列は \(2 N - 4\) 個あり、それぞれが ★★ に等しくなる確率は
\[ \frac { N - 2 } { 2 N - 3 } \cdot \frac { N - 3 } { 2 N - 4 } \]
ですから、
\[ \begin{aligned} E \left \lbrack f \right \rbrack = N - 1 - (2 N - 4) \cdot \frac { N - 2 } { 2 N - 3 } \cdot \frac { N - 3 } { 2 N - 4 } = \frac { N ^ 2 - 3 } { 2 N - 3 } \end{aligned} \]
となり、
\[ \begin{aligned} \mathtt{ans} = \binom { 2 N - 3 } { N - 1 } \frac { N ^ 2 - 3 } { 2 N - 3 } = \binom { 2 N - 4 } { N - 2 } \frac { N ^ 2 - 3 } { N - 1 } \end{aligned} \]
と結論付けられます。
posted:
last update: