ABC 351 G — Hash on Tree

考察

必要なのは、値を変更してから根の答えに届くまでの依存関係を浅くすることである。木の形は固定なので、木DPを計算する順序を一度組み直し、その後は変更箇所から必要な部分だけを再計算したい。

頂点 vv の部分木の値を fvf_v、子の集合を C(v)C(v) とすると、問題の定義は次のとおりである。以降の値と係数の演算はすべて法 998244353998244353 で行う。

fv={Av(v が葉)Av+∏u∈C(v)fu(v が非葉)f_v=\begin{cases} A_v & (v\text{ が葉})\\ A_v+\displaystyle\prod_{u\in C(v)}f_u & (v\text{ が非葉}) \end{cases}

頂点数を NN、更新回数を QQ とすると、毎回このDPを計算する方法は O(NQ)O(NQ) かかる。変更した頂点の祖先だけを計算し直しても、二つの難しさが残る。根から 1→2→3→41\to2\to3\to4 と続く鎖なら、末端の更新が全頂点へ波及する。一方、根 11 に葉 2,3,4,52,3,4,5 が付く星では、葉の更新後に根の積を作り直すだけで子をすべて見る。鎖の「縦に長い依存」と星の「横に広い集約」の両方を、二分木で浅くまとめたい。

まず、鎖では子の値に定数を足す変換を合成すればよいことに注目する。一般の木でも、重軽分解で一本の経路を選び、脇の部分木を先に集約すれば同じ形にできる。頂点 vv を根とする部分木の頂点数を svs_v とし、子のうち sus_u が最大のものを heavy な子、それ以外を light な子とする。同率ならどれを選んでもよい。heavy 辺でつながる極大の経路を heavy path と呼ぶ。

非葉 vv で light な子の値の積を mvm_v とする。heavy な子の値だけを変数 xx として残すと、頂点の変換は Fv(x)=mvx+AvF_v(x)=m_vx+A_v となる。light な子がない場合は mv=1m_v=1。ただし葉では Fv(x)=AvF_v(x)=A_v とする。葉のDPに空積の1を足してはならない。

heavy path の連続区間と、そこに付く light 部分木をまとめたものを path cluster と呼び、未接続の下端の値 xx を上端へ渡すアフィン変換 ax+bax+b の係数 (a,b)(a,b) を持たせる。同じ親へ付く light 部分木の束を point cluster と呼び、その値の積 mm を持たせる。結合は次のように定義できる。

  • compress: 根側の path cluster (ap,bp)(a_p,b_p) と子側の (ac,bc)(a_c,b_c) を結び、(apac, apbc+bp)(a_pa_c,\ a_pb_c+b_p) にする。これは根側の関数を外側に置いた Fp(Fc(x))F_p(F_c(x)) の係数である。
  • rake: 同じ親へ付く二つの point cluster を結び、積 m1m2m_1m_2 にする。
  • light な子を先頭とする heavy path が完成したら、定数成分 bb を point cluster の値として親へ渡す。その path は最下端の葉の定数写像を含むため、下端の変数に依存しない。
  • 頂点 vv を追加するときは、light 側の集約を使って (mv,Av)(m_v,A_v) を作る。葉なら (0,Av)(0,A_v) とする。

鎖の小例では F1(x)=x+A1F_1(x)=x+A_1、F2(x)=x+A2F_2(x)=x+A_2、F3(x)=x+A3F_3(x)=x+A_3、F4(x)=A4F_4(x)=A_4 となる。例えば上半分と下半分を先に compress してから結べば、末端の更新で通る合成の段数を減らせる。星の小例で葉2を heavy な子に選ぶと、light 側は m1=(A3A4)A5m_1=(A_3A_4)A_5、根は F1(x)=m1x+A1F_1(x)=m_1x+A_1 である。light 側の積を rake 木で持てば、葉3の更新時もその祖先の積だけを作り直せる。値が0の子があっても、古い値で割る操作は必要ない。

一般の木では、各 path や子の束を部品個数だけで均等分割すると、path をまたぐたびに深さが増えて全体で O(log⁡2N)O(\log^2 N) になり得る。そこで、参照 Unit と同じく部品が含む元の頂点数を重みにする。

  • rake でまとめる各 light 部分木の重みは、その部分木サイズ sus_u。
  • compress でまとめる頂点部品の重みは wv=1+∑u: light な子suw_v=1+\sum_{u:\,\text{light な子}}s_u。頂点自身と脇の部分木を数えるので、heavy path 全体の重みは先頭頂点の部分木サイズに等しい。

各列の重みの累積和(prefix 重み)を一度作る。再帰で扱う区間の総重みを WW とし、累積重みが W/2W/2 に初めて達する部品を二分探索して pivot とする。pivot 自身を分離し、左右の空でない区間を再帰的に構築した後、「左・pivot・右」の順に高々二回の二分合成でつなぐ。左右それぞれの重みは W/2W/2 以下になり、compress でも path の上下順を保てる。区間は添字で持ち、再帰のたびに列や累積和を作り直さない。

構築は light 部分木から先に行い、その値を渡す point cluster、各頂点の rake 木、頂点追加ノード、heavy path の compress 木の順に作る。各ノードには操作の種類と子・親の参照を保存し、各 AvA_v を使う頂点追加ノードも記録する。これは木DPの計算過程を表す static top tree であり、木の辺追加・削除は扱わない。重み付き構築の高さの証明は以下で補い、構築に要する時間は「計算量と制約」で別に評価する。

初期値は合成木を子から親の順に計算する。クエリで AvA_v が変わったら、対応する頂点追加ノードを現在の light 積と新しい AvA_v から再計算する。その後、元の木ではなく合成木の親を一つずつたどり、保存した子の要約と操作から根まで再計算する。合成木の根は全体の完成 path なので、その定数成分 bb が答え f1f_1 になる。

典型の発動条件

Static Top Tree による動的木 DP

発動条件: 木構造は固定で頂点値だけ更新され、全体の木 DP 値を毎回求めるとき。

木を深さ O(log⁡N)O(\log N) の合成木に変換し、DPの合成則を載せる。合成する要約が定数サイズで、その再計算が定数時間に収まることを確認する。

path cluster の affine 作用

発動条件: 一つの未確定な境界値を通じて cluster 外部と接続し、DP式が一次式に閉じるとき。

cluster を ax+bax+b として表し、compress を関数合成にする。上下順を保った括弧付けの変更なら、結合則によって同じ値を得られる。

問題固有の要素

この問題では子の値の積と頂点値の加算から、heavy な子を変数に残した式がアフィン変換に閉じる。この性質によって、縦の依存と横の集約をそれぞれ compress と rake に載せられる。

別の問題へ持ち帰る視点: 構造が固定で値だけが変わる全体DPでは、境界へ渡す要約を決め、再計算の依存関係を平衡化できないか考える。

正当性

葉の写像 (0,Av)(0,A_v) は問題の葉の値を返す。非葉では light 側の積を係数にした写像へ heavy な子の値を代入すると、元の木DPの式になる。rake は互いに重ならない light 部分木の積を、compress は上下順を保った関数合成を計算するので、子の cluster が正しい要約なら親も正しい。各頂点値を一度だけ使って全体を構築するため、合成木の根は f1f_1 を返す。括弧付けを変えても、積と関数合成の結合則によりこの値は保存される。

重み付き構築の高さも確認する。総重み WW の列中の重み ww の部品を追うと、その部品が pivot になるまで、含まれる再帰区間の重みは毎回半分以下になる。各分割が加える合成は高々二段なので、その部品から列全体までの深さは O(1+log⁡(W/w))O(1+\log(W/w)) である。重い pivot 自身を分離するため、一つの部品が重みの半分を超えていてもこの評価は崩れない。

元の一頂点から根まで追うと、path 内の合成では頂点部品の重みから path 全体の重みへ、rake では light 部分木の重みからその束全体の重みへ増える。これらは入れ子の頂点集合なので、log⁡(W/w)\log(W/w) の和は中間の重みの比が相殺し、全体で O(log⁡N)O(\log N) となる。束に親頂点を加える段階も一段である。各段の定数項は path をまたぐ回数に比例するが、light な子 uu の親を vv とすると sv≥1+2sus_v\geq 1+2s_u なので、その回数も O(log⁡N)O(\log N)。従って合成木の高さは O(log⁡N)O(\log N) である。

一つの AvA_v に直接依存するのは対応する頂点追加ノードだけであり、他に影響し得るノードはその祖先だけである。子の再計算を済ませてから親を更新すれば、各要約の正しさが復元される。よって更新後も根から正しい答えを得られ、再計算するノード数は O(log⁡N)O(\log N) である。

実装上の注意

  • compressの順序は根側の関数が外側、子側が内側。一般には交換できない。
  • 葉は fv=Avf_v=A_v であり、非葉の式へ空積を入れた Av+1A_v+1 ではない。非葉で light な子がないときの係数は1だが、葉の係数は0にする。
  • 子の値が0でも積の木を再計算すればよい。以前の積を古い子の値で割って差し替える実装は使わない。
  • 各 heavy path を単純な要素数で二分すると全体の高さは O(log⁡2N)O(\log^2 N) になり得る。O(log⁡N)O(\log N) 更新を主張するなら元の頂点数で重みを付ける。
  • 元の木は鎖なら深さ N−1N-1 になる。部分木サイズの計算は反復走査などで行い、合成木が浅いことを元の木での再帰の安全性と混同しない。

復習の核

  • 木DPの更新が祖先全体へ広がるときは、未確定な境界値を変数として残し、少数の係数で閉じる変換を探す。
  • 鎖の縦方向は関数合成、星の横方向は子の集約として、計算の依存関係を浅くする。
  • 合成木の高さと構築時間は別に評価する。重み付き分割で高さを証明しても、pivot を探す作業が無料になるわけではない。

計算量と制約

時間

部分木サイズと重軽分解は O(N)O(N)。構築で使う列は、各頂点が一度入る compress 用の列と、各 light 部分木が一度入る rake 用の列なので、部品数の総和は O(N)O(N)。prefix 重みの作成も総計 O(N)O(N) である。

部品数 kk の列では、空でない再帰区間から pivot を一つずつ取り除くため、分割回数は kk 回以下。一回の pivot 探索は二分探索で O(log⁡(k+1))O(\log(k+1))、ノードの追加と結合は O(1)O(1) なので、全列の構築は O(Nlog⁡N)O(N\log N) で抑えられる。初期の要約の計算は、できた O(N)O(N) 個のノードを一度ずつ処理して O(N)O(N)。

各更新は高さ O(log⁡N)O(\log N) の合成木の祖先だけを定数時間ずつ再計算し、答えの取得は O(1)O(1)。従って QQ 回の更新を含む全体は O(Nlog⁡N+Qlog⁡N)O(N\log N+Q\log N) となる。これは公式解説の掲げる O((N+Q)log⁡N)O((N+Q)\log N) と一致する。ここでの前処理の上界は、本文と参照 Unit で説明した prefix 重み・pivot 分離の具体手順から評価したものである。

空間

元の木、部分木サイズ、heavy な子、各頂点と更新ノードの対応に O(N)O(N)。各列の prefix 重みは部品数と同じだけ保持する。各 pivot が作る結合ノードは高々二つで、頂点追加・point への変換も元の頂点あたり定数個なので、合成木は O(N)O(N) ノードである。各ノードの要約と参照は定数サイズ。区間を添字で保持すれば、作業領域を含めて全体で O(N)O(N) となる。

制約との対応

2≤N≤2×1052\leq N\leq 2\times10^5、1≤Q≤2×1051\leq Q\leq 2\times10^5 なので、全体を毎回計算する O(NQ)O(NQ) ではなく、上記の前処理と対数時間更新を用いる。1≤pi<i1\leq p_i<i で根は頂点1。頂点値と更新値は0以上 998244353998244353 未満であり、0を含んでも除算をしない合成則はそのまま使える。制限時間は4秒、メモリ制限は1024 MiB。公式問題文・個別公式解説を2026-10-29に再照合した。過去の Source Revision と確認日時は出典欄のまま保持している。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: rake・compressで動的木DPを保つ

主題
追加で学ぶ技能
    なし
    既習技能
    • Heavy-Light Decomposition: heavy childを選んで木をheavy path列へ分け、path range queryまたはbalanced tree-cluster構築へ接続できる。

    主タグ: Static Top Treeによる動的木DP

    補助タグ: Heavy-Light Decomposition

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

    学習の位置

    体系上の位置: rake・compressで動的木DPを保つ

    • 境界頂点を持つtree clusterの要約と結合を定義し、局所更新後の木DP値を保てる。

    先に読む単元:

    • Heavy-Light Decomposition — ancestor query・LCA・Euler順による部分木区間化で得た考え方と実装を再利用し、Heavy-Light Decompositionの発動条件・正当化・境界を重複なく学ぶ。
    • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 更新を伴わない一回の木DP、および木上pathだけを列へ分けるHeavy-Light Decomposition。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題