ABC 220 E — Distance on Large Perfect Binary Tree

考察

巨大な木を頂点ごとに調べる代わりに、二頂点を結ぶパスの折り返し点を固定して数える。同じ深さの折り返し点は同じ形の部分木を持つので、一頂点分を求めれば、その深さの頂点数を掛けてまとめられる。

パスの折り返し点で分類する

頂点 11 を根とし、根からの距離を深さと呼ぶ。最も深い葉の深さは N−1N-1、頂点数は 2N−12^N-1 である。NN は最大 10610^6 なので、木を実際に作って各頂点から探索する方針は使えない。

ここで、二頂点から根へ向かって親をたどると、途中から同じ経路になることに注目する。二頂点の共通祖先のうち最も深い頂点を 最小共通祖先(LCA) と呼ぶ。頂点自身もその頂点の祖先に含める。二頂点間の唯一のパスは、一方から LCA まで上り、もう一方へ下る形になる。

距離が DD の順序付き対 (i,j)(i,j) に対して、LCA を vv とする。vv から第一端点 ii までの距離を kk と置けば、第二端点 jj までの距離は D−kD-k であり、

D=k+(D−k)D=k+(D-k)

と分かれる。各対に対して vv と kk は一意に決まるので、まず vv を固定して各距離分割の個数を求めればよい。LCA を求めるデータ構造を実装する必要はなく、数える対象を重複なく分けるためにこの概念を使う。

vv の深さを dd とし、その部分木の残り高さを H=N−1−dH=N-1-d と置く。vv から下へ進める辺数の上限が HH である。vv が葉でないとき、二つの子 2v,2v+12v,2v+1 をそれぞれ左の子、右の子と呼ぶ。

両端が LCA と異なる場合

両端とも vv と異なるとき、片方は vv の左の子の部分木、もう片方は右の子の部分木にある。同じ側にあれば、その子も共通祖先となり、vv が最も深い共通祖先であることに反するからである。

両端への距離はともに正で、高さを超えてはならない。従って kk の条件は次の三つになる。

1≤k≤D−1,k≤H,D−k≤H1\leq k\leq D-1,\qquad k\leq H,\qquad D-k\leq H

最後の条件を k≥D−Hk\geq D-H と書き直し、下限どうしの最大、上限どうしの最小を取ると、

L=max⁡(1,D−H),R=min⁡(D−1,H)L=\max(1,D-H),\qquad R=\min(D-1,H)

として、有効な kk は整数区間 L≤k≤RL\leq k\leq R になる。両端を含むので、その個数を C(H)C(H) とすると、

C(H)=max⁡(0,min⁡(D−1,H)−max⁡(1,D−H)+1)C(H)=\max(0,\min(D-1,H)-\max(1,D-H)+1)

である。これは max⁡(0,R−L+1)\max(0,R-L+1) に等しく、外側の最大値は、区間が空の場合を 00 にするためにある。

次に、有効な kk 一つの寄与を求める。まず ii を左側、jj を右側と決める。ii へ向かう最初の一辺は左の子へ進むので固定され、残りの k−1k-1 辺で毎回左右を選べる。従って ii は 2k−12^{k-1} 通りある。同様に jj は 2D−k−12^{D-k-1} 通りあり、独立に選べる。

ii を右側、jj を左側とする割当も同数なので、有効な kk 一つに対する順序付き対は、

2⋅2k−1⋅2D−k−1=2D−12\cdot 2^{k-1}\cdot 2^{D-k-1}=2^{D-1}

通りとなる。これは kk に依存しないため、全ての kk を走査せず、C(H)⋅2D−1C(H)\cdot 2^{D-1} とまとめられる。

kk は第一端点までの距離なので、逆順の対では距離分割も D−kD-k になる。特に DD が偶数で k=D/2k=D/2 のときは距離分割が同じだが、第一端点が左右のどちらにあるかは異なる。順序付き対を数えるため、この場合も割当の係数 22 は必要である。

片端が LCA の場合

k=0k=0 なら i=vi=v であり、jj は vv からちょうど DD 辺下の頂点である。D≤HD\leq H なら、そのような子孫は 2D2^D 頂点ある。k=Dk=D の場合は j=vj=v として同数を数える。

問題では D≥1D\geq 1 なので、この二つの場合は重ならない。片端が vv の対の個数を E(H)E(H) とすると、

E(H)={2⋅2D(D≤H),0(D>H)E(H)= \begin{cases} 2\cdot 2^D & (D\leq H),\\ 0 & (D>H) \end{cases}

となる。LCA と一致する端点へは一辺も進まないので、最初の一辺を固定して導いた 2k−12^{k-1} の式へ k=0k=0 を代入してはいけない。

深さごとにまとめて足す

以上より、一頂点 vv を LCA とする対の個数を F(H)F(H) とすると、

F(H)=E(H)+C(H)⋅2D−1F(H)=E(H)+C(H)\cdot 2^{D-1}

である。同じ深さの頂点は全て残り高さが等しく、深さ dd の頂点は 2d2^d 個ある。従って答えは、

∑d=0N−12dF(N−1−d)\sum_{d=0}^{N-1}2^d F(N-1-d)

を 998244353998244353 で割った余りとなる。

例えば N=3,D=2N=3,D=2 を、この式で追ってみる。

  • 根では H=2H=2。片端が根の対は E(2)=2⋅22=8E(2)=2\cdot 2^2=8 通り。内部の分割は L=R=1L=R=1 の一つで、(2,3),(3,2)(2,3),(3,2) の 22−1=22^{2-1}=2 通りが加わる。根一頂点で計 1010 通りとなる。
  • 深さ 11 では H=1H=1。D>HD>H なので片端が LCA の対はない。L=R=1L=R=1 より、各頂点の二つの子を両端とする 22 通りがある。この深さの頂点は 21=22^1=2 個なので、計 44 通りとなる。
  • 深さ 22 では H=0H=0。子孫を選べず、内部区間も空なので寄与は 00 である。

合計は 10+4=1410+4=14 通りとなり、入力例と一致する。

実装では、次の順で計算する。

  1. M=max⁡(N−1,D)M=\max(N-1,D) とし、pt=2t mod 998244353p_t=2^t\bmod 998244353 を t=0,…,Mt=0,\ldots,M について前計算する。p0=1p_0=1 から順に pt+1=2pt mod 998244353p_{t+1}=2p_t\bmod 998244353 と求める。
  2. 答えを 00 で初期化し、d=0,…,N−1d=0,\ldots,N-1 を走査する。各深さで H,L,R,C(H),E(H)H,L,R,C(H),E(H) を求め、pd(E(H)+C(H)pD−1)p_d(E(H)+C(H)p_{D-1}) を答えへ加える。個数の加算・乗算のたびに法を取る。
  3. 全深さの処理後の答えを出力する。

典型の発動条件

完全二分木の距離分割

木の二頂点間の距離を固定して数えるとき、パスが上りから下りへ切り替わる LCA を固定すると、条件を二本の下向きの距離へ分けられる。片端が LCA の場合と、両端が異なる子の部分木にある場合を分けると、各対の所属が一意になる。

対称構造の深さ集約

頂点数が多すぎても、同じ深さの頂点が同じ形の部分木を持つなら、一頂点の寄与を深さだけで表せる。一頂点分を求め、その深さの頂点数を掛けることで、個々の頂点を列挙せずに集計できる。

問題固有の要素

この木では、左右への距離分割を一つ固定したとき、子孫数の積で指数が足し合わされるため、寄与が分割位置に依存しない。さらに高さ制約の共通部分が整数区間になる。この二つが揃うので、分割の全列挙を区間内の整数の個数へ置き換えられる。

別の問題でも、分割位置を固定した寄与を先に式へ落とし、「寄与は一定か」「有効範囲を端点だけで表せるか」を別々に確認すると、もう一段集約できることがある。

正当性

距離が正の順序付き対には、LCA と、そこから第一端点までの距離が一意に定まる。片端が LCA なら、残り高さが DD 以上のときだけ、もう一方を選ぶ 2D2^D 通りと端点の順序 22 通りを数える。

両端が LCA と異なるなら、両端は異なる子の部分木にあり、距離分割 kk は 1≤k≤D−11\leq k\leq D-1、k≤Hk\leq H、D−k≤HD-k\leq H を満たす。逆に、この条件を満たす kk と左右の割当、各側の端点を選べば、LCA がその頂点で距離が DD の対が必ず得られる。有効な kk は LL 以上 RR 以下の整数であり、その個数は空区間を 00 として C(H)C(H) で求められる。各 kk につき左右の割当と端点の選択で 2D−12^{D-1} 通りを数え、第一端点の側が異なる二つの割当は重複しない。

従って一頂点の寄与 F(H)F(H) は、漏れも重複もなくその頂点を LCA とする対を数える。同じ深さの 2d2^d 頂点の寄与をまとめ、全深さで合計すれば、全ての求める順序付き対をちょうど一度ずつ数えられる。

実装上の注意

  • L,RL,R は通常の整数で求め、C(H)=max⁡(0,R−L+1)C(H)=\max(0,R-L+1) とする。上下限を法上の値に置き換えると、空区間を判定できない。
  • D=1D=1 では内部の分割がなく、親子を両方向に数える項だけが残る。H≥1H\geq 1 かつ D=2HD=2H なら内部区間は k=Hk=H の一点、D>2HD>2H なら部分木内の最大距離を超えるため寄与は 00 である。葉の H=0H=0 でも同じ式で 00 になる。
  • 法を取った C(H)pD−1C(H)p_{D-1} と E(H)E(H) の和も法で縮めてから pdp_d を掛ける。C++ では各乗算を64 bit整数で行い、巨大な整数としての 2N2^N や木自体を生成しない。

復習の核

  • 木のパスを数えるときは、折り返し点を一意に固定し、そこから両端への距離へ分解する。
  • 対称な対象は一つの寄与と個数に分ける。さらに分割位置ごとの寄与が一定なら、有効な位置の個数だけを求める。
  • 順序付き対では、距離が等しい二端点でも逆順は別の対になる。距離分割と左右の割当を混同しない。

計算量と制約

時間

O(N+D)O(N+D)。M=max⁡(N−1,D)M=\max(N-1,D) までの二冪の前計算に O(M)O(M)、全 NN 深さの集計に O(N)O(N) かかる。各深さでは区間の端点と個数を定数回の演算で求め、距離分割 kk を走査しない。

空間

O(N+D)O(N+D)。二冪を保存する長さ M+1M+1 の配列が必要で、深さの集計に使う補助変数は O(1)O(1) 個である。

制約との対応

公式制約は 2≤N≤1062\leq N\leq 10^6、1≤D≤2×1061\leq D\leq 2\times 10^6。前計算の配列は最大 2×106+12\times 10^6+1 要素、深さの走査は最大 10610^6 回で済む。頂点数 2N−12^N-1 に依存する処理は行わない。木全体の最大距離 2(N−1)2(N-1) より DD が大きい場合も、全ての深さの寄与が 00 になる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

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

    主タグ: 寄与の数え上げと順序交換

    補助タグ: 暗黙・対称な完全二分木の深さ算術 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

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

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題