ABC 321 E — Complete Binary Tree

考察

heap番号のtreeでは頂点vから下へd段の子孫labelが連続区間[v·2^d,(v+1)·2^d)になる。Xから距離Kの頂点Yは、そのLCAがX自身か、Xの各ancestorのいずれかという高々tree高さ個のcaseへ一意に分かれる。ancestor zをLCAとするcaseは、zから残りd段の全子孫からXへ向かうchild subtree分を引けば数えられる。countDesc(v,d)はmax(0,min(N+1,(v+1)2^d)-v2^d)で、label上限Nとの区間intersectionだけになる。Xからu段上のancestor zについてd=K-uが0ならz自身1個、d>0ならcountDesc(z,d)-countDesc(child,d-1)が寄与する。u=0、すなわちLCA=XのcaseはcountDesc(X,K)として最初に数える。

採用する候補: Xからrootまでancestorを算術で列挙し、各ancestorをpathの折返し点とするcaseを子孫label区間の長さでO(1)計数する。

Nが10^18でもtree高さは約60で、頂点やedgeを生成せず各testを処理できる。

棄却する候補: 頂点Xから通常のBFSをK layer行う。

Nが最大10^18でtreeを明示できず、Kも非常に大きい。

棄却する候補: 深さがdepth(X)±Kの全labelを数える。

同じ深さ差でもLCA位置によりXからの距離が異なり、不要な別subtreeを含む。

overflowを避けるcountDesc(v,d)を用意し、まずanswer=countDesc(X,K)とする。child=X,z=floor(X/2),u=1からz=0またはu>Kまで上る。d=K-uが0なら1を加え、正ならcountDesc(z,d)-countDesc(child,d-1)を加える。その後child=z,z=floor(z/2)へ更新し、各testのanswerを出力する。

典型の発動条件

implicit complete binary tree

発動条件: 親i/2・子2i,2i+1で巨大treeが番号だけ与えられるとき。

子孫levelを連続label区間として数える。

ancestor位置での距離case分解

発動条件: 固定始点から距離Kの頂点をrooted treeで数えるとき。

pathが上へ何段進んでから別の枝へ下るかをancestorごとに分ける。

全体subtreeから進入branchを引く

発動条件: LCAを特定ancestorに固定し、始点側branchを除外したいとき。

ancestorのd段子孫数からpath childのd-1段子孫数を引く。

問題固有の要素

heap labelでは同じ深さの子孫が区間になるため、通常ならsubtree size前計算が必要な距離計数を端点2つの算術へ変えられる。

別の問題へ持ち帰る視点: implicit treeの番号規則から、depth固定のsubtreeがinterval・等差列などの数えやすい集合にならないか確認する。

正当性

距離Kの相手をLCAがXか各祖先かで一意分類する。祖先z側の残り深さ子孫からX方向の子孫だけ除けばLCAが正確にzの頂点を得る。heap子孫は連続区間なのでNで切って数え、互いに素な全場合を足す。

実装上の注意

  • 2^dやv·2^dが64bitを超える前に、dが十分大きい・v>N>>dならcount 0と判定してshift overflowを避ける。
  • KはN-1までで64bit値なのでint loop上限に変換せず、実際のancestorが尽きる約60回だけ回す。

復習の核

  • Xの子孫case、親自身case、祖先の反対側subtree caseを小さいheap treeに色分けし、同じ頂点を重複せず全て数えるか確認する。

計算量と制約

時間

Nまでのheap木の高さ h=⌊log₂N⌋。祖先列挙と区間算術で各質問 O(h)。

空間

木を生成せず O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq T \leq 10^5; 1\leq N \leq 10^{18}; 1\leq X \leq N; 0\leq K \leq N-1; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 対称性・深さ・label区間で巨大な完全二分木を数える

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

      主タグ: 暗黙・対称な完全二分木の深さ算術

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

      学習の位置

      体系上の位置: 対称性・深さ・label区間で巨大な完全二分木を数える

      • 同じ深さの対称性と2冪で距離splitを集約するか、heap番号の祖先case分解と子孫label区間を使い、巨大な完全二分木を展開せず数えられる。

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

      • 子を明示した一般木の木DP・rerooting、およびLCA・Euler順・HLD・virtual treeを実装するpath query。完全二分木でも個々の頂点を列挙する処理。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題