ABC 264 Ex — Perfect Binary Tree

考察

深さdの完全二分木には2^(d+1)−1頂点が必要なので、N≤30万では高さを対数個に制限できる。親番号が常に小さいため番号順に追加すると新頂点は既存木の葉となり、その頂点を含む新しい構造だけが祖先上で増える。各prefixで全DPを計算し直す代わりに、この差分だけを伝播できないか考える。

dp[v][d]をv根・深さdの完全二分木数、csum[v][d]を子のdp[w][d]の総和とする。追加済みの頂点ではdp[v][0]=1。深さd≥1では異なる二子の深さd−1の木を一つずつ選ぶため、子wのdp[w][d]だけがdelta増えたとき、親のdp[p][d+1]の増分はdelta×(csum[p][d]−dp[w][d]の旧値)となる。新しい一子側の選択を、それ以外の子の全選択と組み合わせる式である。

求めるのは根1を含む選択だけなので、prefix kの答えはΣ_{d=0}^D dp[1][d]である。全頂点のdpを足してはいけない。D=⌊log₂(N+1)⌋−1は辺数で測った最大深さで、深さ0は一頂点だけの木。まだ追加していない頂点のdpと全csumを0にし、頂点1を追加してdp[1][0]=1、最初の答え1から始める。

新頂点i≥2を加える処理は、v=i,d=0,delta=1として次を繰り返す。代入の前後を固定すると、他の子の和から新値を誤って引くことを避けられる。

old = dp[v][d]
dp[v][d] += delta
if v == 1: answer += delta; stop
if d == D: stop
p = P_v
next = delta * (csum[p][d] - old)
csum[p][d] += delta
v = p; d += 1; delta = next

全更新は法998244353。deltaが0になった時点で打ち切ってよいが、その前にcsumへの現在deltaを反映する。rootへ到達した差分だけanswerへ加え、各追加後のanswerを一行出力する。根以外の一頂点木は次の組合せの部品であり、直接答えに加えない。

親が全て1の3頂点なら答えは1,1,2。最後の2は{1}と{1,2,3}だけであり、{2},{3}は数えない。一本道なら子二本の組が一度もできないので全prefixの答えが1になる。

典型の発動条件

指数サイズ構造による深さ上界

発動条件: 深さに対して必要要素数が指数増加し、全体サイズに強い上限があるとき。

完全二分木の深さを定数程度に切り、祖先更新回数も同じ上界で抑える。

木DPの差分祖先伝播

発動条件: 葉が逐次追加され、一つの子部分木のDP変化が祖先だけへ影響するとき。

各層の増分を計算し、親の集約値とDPへ反映して次の祖先へ渡す。

異なる二子選択の総和維持

発動条件: 親状態が異なる二つの子から一項ずつ選ぶ積の総和で定義されるとき。

新しい一子側の値に、それ以外の子の値総和を掛けて追加分だけ求める。

問題固有の要素

実際の根から深さ20以上にある新頂点は、根付き完全二分木に含めるなら高さ20以上を強制するため、全更新を省略できる。

別の問題へ持ち帰る視点: 局所DPの高さ上限だけでなく、更新点の実木上の深さからその更新が答えへ届き得るかも枝刈りする。

正当性

深さdの完全二分木は異なる二子の深さd−1解の積。子wの増分Δだけ変わると新組はΔと他子総和の積になる。旧dp_wを除いてからcsumを更新すれば同じ子を二度選ばない。新頂点を含む構造だけ増え、必要サイズ2^(d+1)−1の上界で伝播打切り可能。 dp[v][0]はvが追加された時だけ1にする。根1を含む全合法集合は根の深さdにより排他的に分類されるので、答えはΣ_d dp[1][d]。差分伝播で根の成分が増える時だけanswerへ加算すると各prefixの答えを重複なく更新できる。

実装上の注意

  • Dは辺数で測った深さ。dpの初期値は未追加頂点を0、追加した頂点だけdp[v][0]=1。
  • 他子の和はcsum[p][d]−dp[v][d]の旧値。次のdeltaを計算してからcsumへ現在deltaを加える。
  • 出力はrootのdpの和。全頂点分の和を使わず、N個のprefixそれぞれを出力する。

復習の核

  • 求める構造の最小サイズが深さに対して指数増加するなら、制約から実用的な深さ定数を先に導く。
  • 動的木DPでは全祖先状態を再計算せず、変更された一子の差分と他子集約値から親差分を出す。

計算量と制約

時間

N頂点、最大完全二分木深さD=⌊log₂(N+1)⌋−1。番号順追加ごと高々D祖先へ一差分伝播し、葉の追加を含め O(N(D+1))。

空間

dpとchild sum O(N(D+1))。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: All values in input are integers.; 1 \le N \le 3 \times 10^5; 1 \le P_i < i

出典

分類・前提・執筆情報

掲載状態: 収録済み

Perfect Binary Tree の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 根付き木DP・部分木集約

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 根付き木DP・部分木集約

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 根付き木DP・部分木集約

      • 根付き木で子側の状態を合成し、部分木または木全体の値を求められる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題