AtCoder Grand Contest 079 A問題メモ
久々にARC以上で正の点数を得た。
A - Tree Contraction Sequence
問題文
- $N$ 頂点からなる根付き木があります.頂点には $1,2,\ldots,N$ の番号がついており,根は頂点 $1$ です.各頂点 $v$ $(2 \leq v \leq N)$ の親は頂点 $P_v$ であり,$1 \leq P_v \lt v$ を満たします.
- また,各頂点は整数列を持っています.最初,頂点 $v$ の持つ列は $(v)$ です.
- これから次の操作を $N-1$ 回行います.
- $2 \leq v \leq N$ を満たす頂点のうち,これまでの操作で選んでいない頂点 $v$ を選び,現在の木におけるその親を $u$ とする.
- 頂点 $u$ の列の末尾に,頂点 $v$ の列を連結する.
- 頂点 $v$ をその親 $u$ に縮約する.すなわち,頂点 $v$ を削除し,その子をすべて頂点 $u$ の子にする.
- すべての操作を終えたとき,残った頂点 $1$ の列が $(1,2,\ldots,N)$ と一致する操作列の個数を,$998244353$ で割った余りを求めてください.ここで,各回で選ぶ頂点の列が異なる操作列は異なるものとして数えます.
- 1 つの入力につき,$T$ ケースを解いてください.
制約
- $1 \leq T \leq 125000$
- $2 \leq N \leq 250000$
- $1 \leq P_v \lt v$ $(2 \leq v \leq N)$
- $T$ ケースにわたる $N$ の総和は $250000$ 以下である.
- 入力される数値はすべて整数である.
解法
①
/|\
② ③ ⑥
/\ |
④⑤⑦
操作の一例
④ → ② → ⑦ → ⑤ → ③ → ⑥
① (1,2) (1,2) (1,2) (1,2,3,4,5) (1,2,3,4,5,6,7)
/ | \ | \ | \ | \ \
②(3,4) ⑥ (3,4) ⑥ (3,4) (6,7) (3,4,5) (6,7) (6,7)
| | | | |
⑤ ⑦ ⑤ ⑦ ⑤
例えば⑤は、③を親として持つが、④を先に③にくっつけないといけないので、④の前に操作できない。
この「④→⑤」という順番の制約は、③を先に操作して親頂点が変わったところで、変わらない。
一方、②の前には操作できる。$(3,4,5)$ という列を先に作って、②はその後、ということはできる。
⑥は①を親として持つが、⑤がなんやかんやあって①にくっつけられるまでは操作できない。
その時点では必然的に②~⑤が全て操作されていることになるので、⑥はそれら全ての後でないとダメ、ということになる。
操作順の制約を整理すると、
- $v$ の祖先 $a$ のうち、以下の条件を満たす中で番号最大の頂点を $f(v)$ とする。
- $a$ の部分木に、$a+1~v$ の頂点が全て存在する。
- この時、$v$ は $f(v)+1~v$ の中では最後に操作しなければならない。
- $2~f(v)$ の間との制約は特にない。
- $v+1$ 以降の間との制約は、そちらが $v$ になった時に考えればよい。
全ての順列のうち、$f(v)+1~v$ の中で $v$ が最後に来る確率は $\frac{1}{v-f(v)}$ になる。
よって、以下の手順で答えとなる。
- 答えを $Ans=(N-1)!$ とする。
- $v=2,3,...,N$ の順に、$f(v)$ を求め $Ans$ を $v-f(v)$ で割る。
$f(v)$ は、$v$ が小さい方から求めていける。交差することはない($f(a) \lt f(b) \lt a \lt b$ のようにはならない)ので、一度計算したところはスキップできる。
- $P_v=v-1$ の場合、$f(v)=v-1$
- そうでない場合、
- $a=P_v$ とする。
- $\min(f(a+1),f(a+2),...,f(v-1)) \lt a$ である間、以下を繰り返す
- $a ← \min(f(a+1),f(a+2),...,f(v-1))$
- $f(v)=a$ とする。
各頂点が何らかの $v$ に対して途中経過の $a$ となる回数は均して $O(1)$ 回なので(たぶん)、 セグ木などで管理すれば全体 $O(N \log{N})$ で求められる。

