ABC 337 G — Tree Inversion

考察

数える組を固定し、その組がどの根の答えに寄与するかを考える。経路上にあるかを頂点を取り除いた後の連結成分で言い換えると、寄与先を部分木またはその補集合へまとめられる。根を一つずつ変えて数え直す代わりに、同じ寄与を受け取る根へ一括で加算する。

経路の条件を、寄与する根の集合へ変える

求める答えを f(u)f(u) とする。これは、uu から vv への経路に ww が含まれ、かつ v<wv<w を満たす組 (v,w)(v,w) の個数である。根ごとに全組を調べる方針では、経路判定を高速にできても組の列挙だけで間に合わない。そこで一組 (v,w)(v,w) を固定し、条件を満たす根 uu をまとめて求められないかと考える。

木から ww を取り除き、vv が属する連結成分を CC とする。u≠wu\ne w のとき、uu が CC の外にあれば、uu から vv への経路は必ず ww を通る。uu が CC 内にあれば、その経路は CC 内で完結する。また、u=wu=w のときも経路の端点として条件を満たす。したがって、寄与する根は、元の全頂点から CC を除いた集合である。この補集合には ww 自身も含める。

例えば2頂点を辺 1–21\text{–}2 で結んだ木では、調べる組は (v,w)=(1,2)(v,w)=(1,2) だけである。w=2w=2 を取り除いた後の vv 側の成分は {1}\{1\} なので、寄与する根は {2}\{2\}。答えは (f(1),f(2))=(0,1)(f(1),f(2))=(0,1) となる。この補集合への加算だけで自己根 u=wu=w も数えるため、さらに f(w)f(w) へ w−1w-1 を足すと二重計上になる。

固定した根で、二種類の区間更新に分ける

求めたい根 uu とは別に、区間を作るための固定根を頂点1とする。以下の親・子・部分木はすべてこの固定根に対するものである。頂点 xx 自身とその子孫の集合を SxS_x と書く。

DFSの行きがけに各頂点を一度だけ並べる。0始まりの入場位置を tin⁡[x]\operatorname{tin}[x]、部分木の処理を終えた時点の次の位置を tout⁡[x]\operatorname{tout}[x] とすれば、SxS_x は半開区間 [tin⁡[x],tout⁡[x])[\operatorname{tin}[x],\operatorname{tout}[x]) に対応する。出場時には位置を増やさない。

今度は頂点 ww を固定する。ww を取り除いた成分は、各子 cc の部分木 ScS_c と、親方向の成分である。後者は SwS_w の外側であり、ww が固定根なら空になる。必要な個数を

qw=#{v∈Sw∣v<w},kc=#{v∈Sc∣v<w}q_w=\#\{v\in S_w\mid v<w\},\qquad k_c=\#\{v\in S_c\mid v<w\}

と定める。kck_c は現在処理している ww の子に対して求める値である。小さい頂点番号は全体に w−1w-1 個あるので、親方向の個数は w−1−qww-1-q_w 個になる。

  • 子 cc の方向:v∈Scv\in S_c となる組は kck_c 個あり、寄与先は ScS_c 以外全部である。全体に +kc+k_c、ScS_c の区間に −kc-k_c を加える。
  • 親の方向:vv が SwS_w の外にある組は w−1−qww-1-q_w 個あり、寄与先は SwS_w である。SwS_w の区間に +(w−1−qw)+(w-1-q_w) を加える。

この二種類の更新先には、いずれも ww が含まれる。子の部分木は SwS_w から ww を除いた集合を分割し、w<ww<w は成立しないので、∑c: wの子kc=qw\sum_{c:\,w\text{の子}}k_c=q_w である。したがって自己根 ww へは、これらの更新から合計

∑c: wの子kc+(w−1−qw)=w−1\sum_{c:\,w\text{の子}}k_c+(w-1-q_w)=w-1

が届く。自己根への別加算は行わない。自己根だけを先に数える別の規約も可能だが、その場合は他の全更新先から ww を除く必要がある。

三枝の独自例として、辺が 3–1,3–2,3–43\text{–}1,3\text{–}2,3\text{–}4 の木を考える。w=3w=3 を取り除くと成分は {1},{2},{4}\{1\},\{2\},\{4\} になる。小さい頂点 v=1,2v=1,2 の寄与先は次のとおりである。

組 (v,w)(v,w)vv 側の成分寄与する根の集合
(1,3)(1,3){1}\{1\}{2,3,4}\{2,3,4\}
(2,3)(2,3){2}\{2\}{1,3,4}\{1,3,4\}

固定根を1とすると、S3={3,2,4}S_3=\{3,2,4\}、q3=1q_3=1、k2=1k_2=1、k4=0k_4=0。子2の方向から全体へ +1+1、S2S_2 へ −1-1、親方向から S3S_3 へ +1+1 と更新する。頂点番号順に届く寄与は (1,1,2,2)(1,1,2,2) で、表の二組を根ごとに数えた結果と一致する。特に自己根3には、二組の分だけちょうど2が届く。

頂点番号の昇順に数え、差分配列へ加える

残る課題は、部分木内の「番号が ww 未満」の個数を高速に数えることである。Euler順を添字とするFenwick Tree(BIT)を用意し、頂点番号 w=1,2,…,Nw=1,2,\ldots,N の順に処理する。処理済みの頂点だけを位置 tin⁡[v]\operatorname{tin}[v] に1として登録しておけば、ww の処理直前にBITへ入っているのはちょうど v<wv<w の頂点である。

登録済みなら1、未登録なら0となる配列を bb とし、BITの接頭辞和を B(t)=∑0≤i<tb[i]B(t)=\sum_{0\leq i<t} b[i] とする。区間 [l,r)[l,r) 内の登録済み頂点数は B(r)−B(l)B(r)-B(l)。これを使って qwq_w と各子の kck_c を求める。これらの問い合わせをすべて終えてから、頂点 ww をBITへ登録する。自分を先に登録すると qwq_w に余分な1が入り、親方向の個数が崩れる。

答え側では、長さ N+1N+1 の差分配列 dd を0で初期化する。区間 [l,r)[l,r) に値 aa を加える操作は、d[l]+=ad[l]\mathrel{+}=a、d[r]−=ad[r]\mathrel{-}=a で表す。各 ww で、取得した個数を次のように反映する。

  1. 各子 cc について、全体の区間 [0,N)[0,N) に kck_c を加え、[tin⁡[c],tout⁡[c])[\operatorname{tin}[c],\operatorname{tout}[c]) に −kc-k_c を加える。
  2. [tin⁡[w],tout⁡[w])[\operatorname{tin}[w],\operatorname{tout}[w]) に w−1−qww-1-q_w を加える。
  3. BITの位置 tin⁡[w]\operatorname{tin}[w] に1を加え、次の頂点番号へ進む。

全頂点を処理した後に差分配列の累積和を一度取る。Euler順の位置 ii の値は ∑j=0id[j]\sum_{j=0}^{i}d[j] なので、各頂点 uu の答えは

f(u)=∑j=0tin⁡[u]d[j]f(u)=\sum_{j=0}^{\operatorname{tin}[u]}d[j]

として頂点番号順に出力する。BITは個数を数えるため、差分配列は全根へ寄与を届けるために使い分ける。後者には途中の問い合わせがないため、区間加算用の別の木構造は要らない。

典型の発動条件

Euler tourによるsubtree区間化

寄与先が部分木、またはその補集合になるときに使う。DFSの入場順では部分木が連続区間なので、部分木への加算は一区間、補集合への加算は「全体に加え、その部分木から引く」で表せる。頂点を除いた成分と、その頂点自身を含む補集合を区別することが重要である。

offline二次元counting

「ある添字区間内で、値がしきい値未満の要素数」を何度も求め、問い合わせを事前に並べ替えられるときに使う。値の昇順に要素を登録すれば、しきい値の条件を処理順で満たし、残る区間条件だけをBITで数えられる。今回なら値は頂点番号、添字はEuler順であり、厳密不等号に合わせて問い合わせを登録より先に行う。

問題固有の要素

経路に含まれる頂点 ww に注目し、ww を取り除いたときの vv 側の成分を考えることが鍵になる。その成分内の根からは ww を通らずに vv へ行けるため、寄与先は成分の補集合になる。根ごとの数え上げを、組ごとの寄与先への更新へ切り替えることで、全根の答えを一緒に求められる。

成分の補集合を部分木と「部分木以外全部」に分ける方針は、個別公式解説に基づく。本稿では頂点番号の昇順にBITへ登録する実装を採り、自己根への寄与の確認・二つの小例・上の区間更新手順と以下の証明を独自に補っている。公式問題文と個別公式解説は2026-10-29に再照合した。

正当性

任意の組 (v,w)(v,w)、v<wv<w を固定する。ww を取り除いた後に vv が属する成分を CC とすると、根 uu が CC 内にある場合、経路はその成分内に収まり ww を含まない。u≠wu\ne w が別の成分にある場合は、木の経路の一意性より ww を通る。また u=wu=w も経路の端点なので条件を満たす。従って、この組が寄与する根は元の全頂点における CC の補集合と厳密に一致する。

固定根に対する子 cc の方向では C=ScC=S_c なので、全体への加算と ScS_c からの減算により、条件を満たす根だけに1が残る。親方向では CC が SwS_w の外側なので、SwS_w への加算が同じ役割を果たす。v<wv<w の各頂点はこれらの成分のちょうど一つに属するため、個数 kck_c または w−1−qww-1-q_w による集約には漏れも重複もない。自己根 u=wu=w も各組の補集合に一度だけ含まれ、合計 w−1w-1 が届く。別途の自己根加算は不要である。

各 ww の問い合わせ時、BITには番号が ww 未満の頂点だけが登録されている。Euler区間内の和は定義どおりの qw,kcq_w,k_c を返す。さらに差分配列の累積和は各区間更新を、その半開区間内の位置だけへ反映する。よって最終的な f(u)f(u) は、元の条件を満たす全組を正確に一度ずつ数えた値になる。

実装上の注意

  • 頂点番号は1始まり、Euler順の位置は0始まりと区別する。番号が ww 未満の頂点総数は w−1w-1 個である。
  • qwq_w と全 kck_c の取得が済むまで、ww をBITへ登録しない。固定根では q1=0q_1=0 で親方向の加算も0。葉では子方向の更新がなく、qw=0q_w=0 なので自己根に w−1w-1 が届く。
  • 差分配列には右端 NN への書き込み用の要素も確保する。Euler順で累積した答えは tin⁡[u]\operatorname{tin}[u] から取り出し、頂点番号順へ戻して出力する。
  • 差分には減算があるため符号付き整数を使う。答えの上限は (N2)\binom{N}{2} で32 bit整数を超えるので、差分・累積和・答えには64 bit整数を使う。
  • 鎖状の木ではDFSの深さが NN になる。再帰の上限が厳しい環境では、入場・出場を区別する明示スタックでEuler順を構築する。

復習の核

  • 全根について経路条件を数えるときは、組を固定し「どの根へ寄与するか」に問いを変える。
  • 頂点を取り除いた成分の補集合には、取り除いた頂点自身も入る。端点への別加算と混ぜず、2頂点の木で二重計上を確かめる。
  • 区間と値の二条件がある数え上げでは、一方を処理順で満たせないか考える。厳密不等号は問い合わせと登録の順序に反映する。

計算量と制約

時間

隣接リストとEuler順の構築に O(N)O(N)。部分木の個数問い合わせは、各頂点の qwq_w が NN 回、各親子辺の kck_c が N−1N-1 回で、合計 2N−12N-1 回である。各問い合わせはBITの接頭辞和2回、登録は各頂点1回なので、BITの処理は全体で O(Nlog⁡N)O(N\log N)。差分配列への区間加算は子ごとに2回と頂点ごとに1回、最後の累積和と出力も O(N)O(N)。頂点番号は既に 1,…,N1,\ldots,N なのでソートは不要であり、前処理を含む総時間は O(Nlog⁡N)O(N\log N) となる。

空間

隣接リスト、親子関係、DFS用スタック、Euler順の入退位置、BIT、差分配列、答えがそれぞれ O(N)O(N)。問い合わせや組をすべて保存する必要はなく、全体で O(N)O(N)。

制約との対応

2≤N≤2×1052\leq N\leq 2\times10^5 のため、全組や全根について二乗個の処理はできない。各頂点と各親子辺につき定数回のBIT操作へ集約することで、O(Nlog⁡N)O(N\log N) 時間・O(N)O(N) 空間で処理できる。与えられるグラフが木であることを、経路の一意性と部分木区間化に使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: Euler順による部分木区間化

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

    主タグ: Euler順による部分木区間化

    補助タグ: event・値順のオフライン走査 Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

    体系上の位置: Euler順による部分木区間化

    • Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題