E - Minimize Sum of Distances 解説 by Cyanmond
注: グラフがパスグラフで \(C_1 = C_2 = \cdots = C_N = 10^9\) である場合、 \(f(x)\) の最大値は \(\displaystyle \frac{10^5 \times (10^5 - 1) \times 10^9}{2} \fallingdotseq 5 \times 10^{18}\) となります。これは符号付き 64 bit 整数型に収まりますが \(2\) 倍すると収まらないので、特に解法 2 では一部の実装はオーバーフローする可能性があります。
解法 1
木の重心 という概念が存在します。ABC291-Ex の解説 に性質や存在性の証明、発見アルゴリズムなどが書いてあります。
\(C_1 = C_2 = \cdots = C_N = 1\) の場合、木の重心の一つを \(v\) として \(f(v)\) が答えです。
証明
$v$ ではない頂点 $x$ について考えます。$x$ から木上で $v$ 方向に距離 $1$ 移動した先の頂点を $y$ とします。
$v$ を根としたときの $x$ の部分木のサイズを $s$ として、 $f(y) = f(x) + s - (N - s) = f(x) + 2s - N$ です。また、 重心の性質より $\displaystyle s \leq \frac{N}{2}$ です。そのため、 $f(y) \leq f(x)$ が成り立ちます。
$x$ を $y$ に置き換えてこの議論を繰り返すことで、どの頂点を最初の $x$ にしても $f(x)$ が単調非増加のまま $x=v$ に辿り着きます。よって $f(v)$ が答えであることがわかります。
\(C_1 = C_2 = \cdots =C_N=1\) という条件を取り払ってもほとんど同じです。頂点に重みをつけた重心のイメージで、以下の条件を満たすような頂点 \(v\) を考えます。
- 頂点 \(v\) を根としたとき、\(v\) の子のどの部分木の \(C_i\) の和も \(\displaystyle \frac{1}{2} \sum_{i=1}^{N} C_i\) 以下である。
このとき \(f(v)\) が答えです。答えであることの証明は先ほどと同じような議論をすれば良いです。このような \(v\) が存在することの証明は、重心が存在する証明と同様にできます。
解法 2
全方位木 DP と呼ばれるアルゴリズムで、 \(f(1), f(2), \cdots ,f(N)\) を合わせて \(O(N)\) で求めることができます。全方位木 DP 自体については、 ABC222-F の解説 に詳しいです。
この問題では、部分木の \(C_i\) の和と、重み \(C_i\) のついた距離の和を保持すればよいです。擬似コードとしては以下のようになります。今回の場合、一般の全方位木 DP で一番手間がかかる左右からのマージの実装を適切にサボることができます。
# 配列 sum_c[i]: 頂点 i の部分木の頂点 x について C[x] の総和
# 配列 sum_d[i]: 頂点 i の部分木の頂点 x について C[x] x d(i, x) の総和
# v: 今の頂点
proc dfs(v: int): void =
sum_c[v] = C[v]
sum_d[v] = 0
for t in (children of v):
dfs(t)
sum_c[v] += sum_c[t]
sum_d[v] += sum_c[t] + sum_d[t]
dfs(0)
# 配列 f[i]: f(i)
# v: 今の頂点
# p_sum_c: v の部分木以外の頂点 x について C[x] の総和
# p_sum_d: v の部分木以外の頂点 x について C[x] x d(v, x) の総和
proc rerooting(v, p_sum_c, p_sum_d: int): void =
f[v] = sum_d[v] + p_sum_d
for t in (children of v):
nx_sum_c = p_sum_c + sum_c[v] - sum_c[t]
nx_sum_d = p_sum_d + sum_d[v] - (sum_d[t] + sum_c[t]) + nx_sum_c
rerooting(t, nx_sum_c, nx_sum_d)
rerooting(0, 0, 0)
投稿日時:
最終更新: