ABC 406 F — Compare Tree Weights

考察

木を任意の根で根付き化すると、辺を削除した片側は、その辺の子側頂点を根とする部分木になり、もう片側は全体からその部分木を除いた集合になる。DFS の行きがけ順では任意の部分木の頂点番号が連続区間になるため、頂点重みの一点加算と部分木和は一次元配列の一点加算・区間和へ変換できる。入力時の辺の向きは根付き木の親子と一致しないので、DFS 後に各 edge id について深い側の端点を保存すれば query から部分木を一意に選べる。更新後の全体和 total を同時に増やすことで、補集合の和を別のデータ構造なしに total-sub として得られる。

採用する候補: Euler tour 順の頂点重みを Fenwick tree で管理し、全体重みも別に保持する

edge y の子側部分木和 sub を区間和で求めれば、二成分の差は |total-2sub|。前処理 O(N)、各 query O(log N) である。

棄却する候補: type 2 のたびに対象辺を避けて DFS し、二成分の重みを数え直す

一回 O(N) となり Q=3×10^5 では間に合わず、辺が実際には削除されない固定木を再利用していない。

頂点 1 を根に DFS し tin[v],tout[v],parent と各辺の child を求める。Fenwick tree を初期値 1 で構築し、type 1 は tin[x] へ w 加算して total も更新、type 2 は sub=sum(tin[child]..tout[child]) として abs(total-2sub) を出力する。

典型の発動条件

Euler tour flattening

発動条件: 固定木の部分木に対する更新・集計を列データ構造へ載せたいとき。

DFS 入時刻と退出時刻で各部分木を連続区間にする。

Fenwick tree

発動条件: 一点加算と区間和 query が大量にあるとき。

Euler 順の重みを保持し、prefix sum の差から子側部分木和を得る。

問題固有の要素

辺削除後の二成分を両方集計せず、根を固定して「子部分木」と「全体−子部分木」に非対称化する。

別の問題へ持ち帰る視点: 固定木の辺 query は、各辺を親子のどちら側で代表させるかを前処理すると部分木 query に変換できる。

正当性

辺削除の子側はEuler連続区間であり、その和subを求めれば反対側はtotal−sub。二成分差は|total−2sub|。一点加算でBITとtotalを更新すれば不変条件が保たれる。

実装上の注意

  • 再帰 DFS は N=3×10^5 で stack overflow の恐れがあるため反復 DFSも検討する。重み総和は 64 bit とし、tout の包含/半開区間を統一する。

復習の核

  • 根に接続する辺、葉の辺、chain/star、同一点への連続更新を、辺を実際に除いて成分和を走査する実装と比較する。

計算量と制約

時間

N 頂点、Q 操作。DFS O(N)、各BIT操作 O(log N)、全体 O(N+Qlog N)。

空間

木、Euler順、BIT O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 3 \times 10^5; 1 \leq U_i, V_i \leq N; 1 \leq Q \leq 3 \times 10^5; 1 \leq x \leq N; 1 \leq w \leq 1000; 1 \leq y \leq N-1; All input values are integers.; The given graph is a tree.; There is at least one query of the second type.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

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

    補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

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

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

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題