考察
木を任意の根で根付き化すると、辺を削除した片側は、その辺の子側頂点を根とする部分木になり、もう片側は全体からその部分木を除いた集合になる。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.
出典