AtCoder Grand Contest 079 A問題メモ

AtCoder Grand Contest 079

久々に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})$ で求められる。

Python3

programming_algorithm/contest_history/atcoder/2026/1108_agc079.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0