考察
数える組を固定し、その組がどの根の答えに寄与するかを考える。経路上にあるかを頂点を取り除いた後の連結成分で言い換えると、寄与先を部分木またはその補集合へまとめられる。根を一つずつ変えて数え直す代わりに、同じ寄与を受け取る根へ一括で加算する。
経路の条件を、寄与する根の集合へ変える
求める答えを とする。これは、 から への経路に が含まれ、かつ を満たす組 の個数である。根ごとに全組を調べる方針では、経路判定を高速にできても組の列挙だけで間に合わない。そこで一組 を固定し、条件を満たす根 をまとめて求められないかと考える。
木から を取り除き、 が属する連結成分を とする。 のとき、 が の外にあれば、 から への経路は必ず を通る。 が 内にあれば、その経路は 内で完結する。また、 のときも経路の端点として条件を満たす。したがって、寄与する根は、元の全頂点から を除いた集合である。この補集合には 自身も含める。
例えば2頂点を辺 で結んだ木では、調べる組は だけである。 を取り除いた後の 側の成分は なので、寄与する根は 。答えは となる。この補集合への加算だけで自己根 も数えるため、さらに へ を足すと二重計上になる。
固定した根で、二種類の区間更新に分ける
求めたい根 とは別に、区間を作るための固定根を頂点1とする。以下の親・子・部分木はすべてこの固定根に対するものである。頂点 自身とその子孫の集合を と書く。
DFSの行きがけに各頂点を一度だけ並べる。0始まりの入場位置を 、部分木の処理を終えた時点の次の位置を とすれば、 は半開区間 に対応する。出場時には位置を増やさない。
今度は頂点 を固定する。 を取り除いた成分は、各子 の部分木 と、親方向の成分である。後者は の外側であり、 が固定根なら空になる。必要な個数を
と定める。 は現在処理している の子に対して求める値である。小さい頂点番号は全体に 個あるので、親方向の個数は 個になる。
- 子 の方向: となる組は 個あり、寄与先は 以外全部である。全体に 、 の区間に を加える。
- 親の方向: が の外にある組は 個あり、寄与先は である。 の区間に を加える。
この二種類の更新先には、いずれも が含まれる。子の部分木は から を除いた集合を分割し、 は成立しないので、 である。したがって自己根 へは、これらの更新から合計
が届く。自己根への別加算は行わない。自己根だけを先に数える別の規約も可能だが、その場合は他の全更新先から を除く必要がある。
三枝の独自例として、辺が の木を考える。 を取り除くと成分は になる。小さい頂点 の寄与先は次のとおりである。
固定根を1とすると、、、、。子2の方向から全体へ 、 へ 、親方向から へ と更新する。頂点番号順に届く寄与は で、表の二組を根ごとに数えた結果と一致する。特に自己根3には、二組の分だけちょうど2が届く。
頂点番号の昇順に数え、差分配列へ加える
残る課題は、部分木内の「番号が 未満」の個数を高速に数えることである。Euler順を添字とするFenwick Tree(BIT)を用意し、頂点番号 の順に処理する。処理済みの頂点だけを位置 に1として登録しておけば、 の処理直前にBITへ入っているのはちょうど の頂点である。
登録済みなら1、未登録なら0となる配列を とし、BITの接頭辞和を とする。区間 内の登録済み頂点数は 。これを使って と各子の を求める。これらの問い合わせをすべて終えてから、頂点 をBITへ登録する。自分を先に登録すると に余分な1が入り、親方向の個数が崩れる。
答え側では、長さ の差分配列 を0で初期化する。区間 に値 を加える操作は、、 で表す。各 で、取得した個数を次のように反映する。
- 各子 について、全体の区間 に を加え、 に を加える。
- に を加える。
- BITの位置 に1を加え、次の頂点番号へ進む。
全頂点を処理した後に差分配列の累積和を一度取る。Euler順の位置 の値は なので、各頂点 の答えは
として頂点番号順に出力する。BITは個数を数えるため、差分配列は全根へ寄与を届けるために使い分ける。後者には途中の問い合わせがないため、区間加算用の別の木構造は要らない。
典型の発動条件
Euler tourによるsubtree区間化
寄与先が部分木、またはその補集合になるときに使う。DFSの入場順では部分木が連続区間なので、部分木への加算は一区間、補集合への加算は「全体に加え、その部分木から引く」で表せる。頂点を除いた成分と、その頂点自身を含む補集合を区別することが重要である。
offline二次元counting
「ある添字区間内で、値がしきい値未満の要素数」を何度も求め、問い合わせを事前に並べ替えられるときに使う。値の昇順に要素を登録すれば、しきい値の条件を処理順で満たし、残る区間条件だけをBITで数えられる。今回なら値は頂点番号、添字はEuler順であり、厳密不等号に合わせて問い合わせを登録より先に行う。
問題固有の要素
経路に含まれる頂点 に注目し、 を取り除いたときの 側の成分を考えることが鍵になる。その成分内の根からは を通らずに へ行けるため、寄与先は成分の補集合になる。根ごとの数え上げを、組ごとの寄与先への更新へ切り替えることで、全根の答えを一緒に求められる。
成分の補集合を部分木と「部分木以外全部」に分ける方針は、個別公式解説に基づく。本稿では頂点番号の昇順にBITへ登録する実装を採り、自己根への寄与の確認・二つの小例・上の区間更新手順と以下の証明を独自に補っている。公式問題文と個別公式解説は2026-10-29に再照合した。
正当性
任意の組 、 を固定する。 を取り除いた後に が属する成分を とすると、根 が 内にある場合、経路はその成分内に収まり を含まない。 が別の成分にある場合は、木の経路の一意性より を通る。また も経路の端点なので条件を満たす。従って、この組が寄与する根は元の全頂点における の補集合と厳密に一致する。
固定根に対する子 の方向では なので、全体への加算と からの減算により、条件を満たす根だけに1が残る。親方向では が の外側なので、 への加算が同じ役割を果たす。 の各頂点はこれらの成分のちょうど一つに属するため、個数 または による集約には漏れも重複もない。自己根 も各組の補集合に一度だけ含まれ、合計 が届く。別途の自己根加算は不要である。
各 の問い合わせ時、BITには番号が 未満の頂点だけが登録されている。Euler区間内の和は定義どおりの を返す。さらに差分配列の累積和は各区間更新を、その半開区間内の位置だけへ反映する。よって最終的な は、元の条件を満たす全組を正確に一度ずつ数えた値になる。
実装上の注意
- 頂点番号は1始まり、Euler順の位置は0始まりと区別する。番号が 未満の頂点総数は 個である。
- と全 の取得が済むまで、 をBITへ登録しない。固定根では で親方向の加算も0。葉では子方向の更新がなく、 なので自己根に が届く。
- 差分配列には右端 への書き込み用の要素も確保する。Euler順で累積した答えは から取り出し、頂点番号順へ戻して出力する。
- 差分には減算があるため符号付き整数を使う。答えの上限は で32 bit整数を超えるので、差分・累積和・答えには64 bit整数を使う。
- 鎖状の木ではDFSの深さが になる。再帰の上限が厳しい環境では、入場・出場を区別する明示スタックでEuler順を構築する。
復習の核
- 全根について経路条件を数えるときは、組を固定し「どの根へ寄与するか」に問いを変える。
- 頂点を取り除いた成分の補集合には、取り除いた頂点自身も入る。端点への別加算と混ぜず、2頂点の木で二重計上を確かめる。
- 区間と値の二条件がある数え上げでは、一方を処理順で満たせないか考える。厳密不等号は問い合わせと登録の順序に反映する。
計算量と制約
時間
隣接リストとEuler順の構築に 。部分木の個数問い合わせは、各頂点の が 回、各親子辺の が 回で、合計 回である。各問い合わせはBITの接頭辞和2回、登録は各頂点1回なので、BITの処理は全体で 。差分配列への区間加算は子ごとに2回と頂点ごとに1回、最後の累積和と出力も 。頂点番号は既に なのでソートは不要であり、前処理を含む総時間は となる。
空間
隣接リスト、親子関係、DFS用スタック、Euler順の入退位置、BIT、差分配列、答えがそれぞれ 。問い合わせや組をすべて保存する必要はなく、全体で 。
制約との対応
のため、全組や全根について二乗個の処理はできない。各頂点と各親子辺につき定数回のBIT操作へ集約することで、 時間・ 空間で処理できる。与えられるグラフが木であることを、経路の一意性と部分木区間化に使っている。
出典