E - Minimize Sum of Distances 解説 by en_translator
Note: if the graph is a path graph and \(C_1 = C_2 = \cdots = C_N = 10^9\), then \(f(x)\) can be at most \(\displaystyle \frac{10^5 \times (10^5 - 1) \times 10^9}{2} \fallingdotseq 5 \times 10^{18}\). This does fit in a signed 64-bit integer type, but its double does not, so some implementation of solution 2 may result in an overflow.
Solution 1
There is a concept called a centroid of a tree. The editorial of ABC291-Ex describes the property, proof of existence, and how to find one.
If \(C_1 = C_2 = \cdots = C_N = 1\), the answer is \(f(v)\), where \(v\) is a centroid of the tree.
Proof
Consider a vertex $x$ that is not $x$. Let $y$ be the next vertex you visit when traveling from $x$ toward $v$.
We have $f(y) = f(x) + s - (N - s) = f(x) + 2s - N$, where $s$ is the size of the subtree rooted at $x$ when considering $v$ as the root. Also, by the property of a centroid, $\displaystyle s \leq \frac{N}{2}$. Thus, $f(y) \leq f(x)$.
Replacing $x$ with $y$ and repeating this discussion, one can reach from any initial vertex $x$ to $x=v$ with $f(x)$ always being monotonically non-increasing. Thus, $f(v)$ is the answer.
The situation is almost the same without the constraint that \(C_1 = C_2 = \cdots =C_N=1\). Imaging the centroid with weighted vertices, consider a vertex \(v\) such that:
- considering \(v\) as the root, the sum of \(C_i\) of the vertices in the subtree rooted at any child of \(v\) is not more than \(\displaystyle \frac{1}{2} \sum_{i=1}^{N} C_i\).
Then, the answer is \(f(v)\). We can prove that this is the correct answer in almost the same discussion as before. The existence of such \(v\) can be done in the same manner as that of the centroid.
Solution 2
The algorithm called rerooting DP (Dynamic Programming) enables us to find \(f(1), f(2), \cdots ,f(N)\) in a total of \(O(N)\) time. For more details on the rerooting DP itself, refer to the editorial of ABC222-F.
In this problem, it is sufficient to maintain the sum of \(C_i\) and the sum of distnaces weighted by \(C_i\) for each subtree. The pseudocode would be like the following. In our case, we can appropriately sabotage the most bothering step of merging from left to right.
# Array sum_c[i]: The sum of C[x] over all vertices x in the subtree rooted at vertex i
# Array sum_d[i]: The sum of C[x] x d(i, x) over all vertices x in the subtree rooted at vertex i
# v: current vertex
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)
# Array f[i]: f(i)
# v: current vertex
# p_sum_c: The sum of C[x] over all vertices x not in the subtree rooted at vertex v
# p_sum_d: The sum of C[x] x d(v, x) over all vertices x not in the subtree rooted at vertex v
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)
投稿日時:
最終更新: