ABC 220 F — Distance Sums 2

考察

各始点から独立に距離和を求めると同じ木を何度も探索する。一つの根1についてなら、全頂点の深さの和がそのまま ans(1) になり、同じ DFS で各部分木サイズも得られる。根を親 p から子 c へ一辺移すと、c の部分木内の sub(c) 頂点への距離は1減り、それ以外の N-sub(c) 頂点への距離は1増える。辺 p-c をまたぐ reroot 差分は、近くなる sub(c) 個の -1 と遠くなる N-sub(c) 個の +1 の合計 N-2sub(c) である。

採用する候補: 最初の DFS で ans(1) と部分木サイズを求め、二回目の DFS で ans(c)=ans(p)+N-2sub(c) を全辺へ伝播する rerooting を行う。

根を一辺移した差分が切断された二成分のサイズだけで決まり、各頂点の距離を再計算せず全回答を共有できる。

棄却する候補: 各頂点を始点に BFS または DFS を実行して距離和を足す。

木でも一回の探索に N が必要で、N 個の始点について二乗時間になる。

頂点1を根に DFS し、depth の総和と sub[v] を計算する。ans[1] をその総和で初期化し、親から子へ進むたび ans[child]=ans[parent]+N-2sub[child] を代入して全頂点を出力する。

典型の発動条件

全方位木 DP(rerooting)

発動条件: 各頂点を根にした値が必要で、隣接する二つの根の答えの差を辺の両側の情報から求められるとき。

一つの根で基準値と部分木情報を作り、辺ごとの差分を全頂点へ伝える。

辺切断による寄与差分

発動条件: 根や始点を一辺動かしたとき、対象が辺のどちら側にあるかで寄与変化が一定になるとき。

部分木側と補集合側の個数を数え、距離変化をまとめて加減する。

問題固有の要素

距離和全体の reroot に必要なのは各距離値ではなく、移動した辺の子側に何頂点あるかだけである。

別の問題へ持ち帰る視点: 全始点への集約量では、始点を隣へ動かしたとき各対象の寄与が何種類の差分に分かれるかを調べる。

正当性

根を親から子cへ移すとsub[c]点の距離が1減り、それ以外は1増えるので差N−2sub[c]。初期根の距離和を正確に求め、親答えから子答えを伝える帰納法で全根の距離和を得る。

実装上の注意

  • 距離和は最大で N(N-1)/2 なので 64 bit で持つ。深い path 木では再帰 stack が不足し得るため iterative DFS または stack 設定を検討し、親辺を逆走しない。

復習の核

  • 辺を一本切って子側へ丸を付け、始点を親から子へ移したとき「近くなる個数」と「遠くなる個数」を数えて式を再導出する。

計算量と制約

時間

N 頂点に対して二回走査 O(N)、出力 O(N)。

空間

木、部分木サイズ、答え O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq u_i < v_i \leq N; The given graph is a tree.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Distance Sums 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: rerooting・全方位木DP

主題
  • rerooting・全方位木DP: 子側と親側の寄与の差し替えを定義し、各頂点を根とした答えを求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: rerooting・全方位木DP

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

      学習の位置

      体系上の位置: rerooting・全方位木DP

      • 子側と親側の寄与の差し替えを定義し、各頂点を根とした答えを求められる。

      先に読む単元:

      • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題