対称性・深さ・label区間で巨大な完全二分木を数える

概要

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

巨大な完全二分木を展開せず、同じ深さの対称性と2冪で集約するか、heap番号の祖先移動と深さdの子孫label区間を使って数える。

考え方

heap番号の完全二分木なら、頂点xの深さdの子孫は番号区間[x·2^d,(x+1)·2^d)に入る。存在範囲との共通部分を数えることで、巨大な木を展開せず層を集計できる。

存在する番号を1,…,Nとする。xの深さhの子孫数を C(x,h)=max(0,min(N+1,(x+1)2^h)−x2^h) とし、h<0やx>Nなら0にする。xから距離Kの頂点は、まず子孫C(x,K)。次にxの祖先aへj≥1辺上がる各caseで、K=jならa自身を一個、K>jならxへ向かう子とは反対の子sを根とするC(s,K−j−1)を加える。LCA(x,対象)がaであるcaseへ一意に分けているので、重複しない。

祖先はxを2で割って根まで辿れる。深さを超えるhでは対象範囲と交わらないため早期に0を返し、巨大shiftを実行しない。木が完全な全層を持つなら各C=2^hとなり、対称な距離splitも同じ式から得られる。

成立条件と計算量

祖先をたどる回数はO(log N)。同じ距離の頂点を兄弟部分木へ分ける場合、重複しない層を選ぶ。乗算・shift前に上限を検査し、存在しない番号や距離0も扱う。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。二冪・深さ・heap番号の区間を使い、巨大な完全二分木を展開せず数える。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-implicit-binary-tree

習得する技能

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

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

指数個の頂点を持つ完全二分木を展開せず、深さごとの対称性と2冪で集約するか、heap番号の祖先移動と深さ別子孫label区間で数える。

このUnitでは扱わないもの

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

根拠