考察
treeを一つroot化すると、ある頂点から全頂点への重み付き距離和と各subtreeのC総和が分かれば、rootをedge一本隣へ移した時の値を差分計算できる。parent vからchild uへ基準点を移すと、subtree(u)内の各距離は1減り、それ以外は1増える。total weightをT、sub[u]をsとすればf(u)=f(v)-s+(T-s)=f(v)+T-2sである。
採用する候補: subtree weightを求めた後、rerooting式で全f(v)を計算する
二回のDFSで全頂点の目的値をO(N)計算し、その最小を取れる。
棄却する候補: 各vからDFSして距離和を計算する
一頂点O(N)をN回行いO(N^2)になる。
頂点1をrootにDFSしdepthとsubtree weight sub[v]を求め、f(1)=ΣC_v·depth[v]を計算する。二度目のDFSで各parent-childにf[child]=f[parent]+T-2sub[child]を適用し、全fの最小を出力する。
典型の発動条件
rerooting DP
発動条件: rootに依存する全頂点への距離和を全rootについて求めたい。
edgeを跨いだ時に近づくsubtree量と遠ざかる補集合量の差で更新する。
重み付きsubtree集計
発動条件: 各頂点が異なるmultiplicity C_iで距離へ寄与する。
頂点数の代わりにsubtree内C総和をpostorderで持つ。
問題固有の要素
unweighted centroidのsize式をC重みへそのまま一般化し、移動差の符号からweighted centroidも解釈できる。
別の問題へ持ち帰る視点: 距離和rerootingは対象数を任意の非負weight総量に置き換えて成立する。
正当性
一辺越えて根を子へ移すと子側重み総和subの距離が1減り、外側重みT−subが1増えるため差T−2sub。初期ΣC_v depth[v]から全rootを厳密に更新し最小を取る。
実装上の注意
- fは約5×10^18まで達するのでsigned 64bitを使い、2×fのような不要な倍化を避ける。N=1ではf=0である。
復習の核
- path、star、重い頂点一つ、N=1を全点BFSの距離和と比較しreroot差を確認する。
計算量と制約
時間
N 頂点、二回走査 O(N)。
空間
木、部分木重み、全根目的値 O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq A_i, B_i \leq N; The given graph is a tree.; 1 \leq C_i \leq 10^9
出典