Official
R - Subtree with Lower Limit Editorial
by
R - Subtree with Lower Limit Editorial
by 
highlighter
\(u=2,3,\ldots,N\) について，頂点 \(u\) の親を \(par_{u}\) で表す．
明らかに \(par_{u} \lt u\) が必要．
また， \(par_{u} \lt u\) を満たすとき，それに対応する根付き木がちょうど一つ存在する．
証明
$u=2,3,\ldots,N$ について，頂点 $u$ と頂点 $par_{u}$ を結んだグラフは， $u$ から $par_{u}$ への移動を繰り返すと必ず頂点 $0$ に到達することから連結である． 辺の本数が $N-1$ 本であることも踏まえて，これは木を成す． $par$ はこのグラフ以外を表すことはできないので，示せた．異なる \(par\) からは異なる木が生成されるので，答えは \(par_{u}<u\) を満たす正整数列 \(par\) の個数であり，これは \(1 \times 2 \times \cdots \times (N-1) = (N-1)!\) 個．
posted:
last update: