PROBLEM LINK:
Author: Satyam Kumar
Tester: Parth Mittal
Editorialist: Satyam Kumar
DIFFICULTY:
HARD
PREREQUISITES:
Trees, Convex Hull Trick, DFS Order
PROBLEM:
Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.
EXPLANATION:
Let’s find the best solution on removing some edge e = (u, v) such that u is the parent of v. The best solution would involve reattaching some node x in the subtree of v (including v) to some node y in the residual tree (after removing the edge e) containing u. Now, y is the vertex with the smalle
st distance to the vertex 1. For x, it is the vertex which is the best (least cost) root for the subtree of v.
For the best root for some tree:
Let C(T, u) denote the cost of a tree T being rooted at u.
Let’s say that the tree T was originally rooted at some u(so we can precompute C(T, u)), and we want to shift the root to p, where p is a child of u.
Then it is not hard to see that C(T, p) = C(T, u) + (\texttt{size}(T) - 2\cdot \texttt{sub\_tree\_size}(p))\times (\texttt{edge\_weight}(u, p))
Further, let us say that p_k is an arbitrary descendent of p_0, and the nodes p_1 \dots p_k occur on the path from p_0 to p_k, then by repeated application of the above form, we get
C(T, p_k) = C(T, p_0) + \sum_{i = 1}^{k}\left((\texttt{size}(T) - 2\cdot \texttt{sub\_tree\_size}(p_{i}))\times (\texttt{edge\_weight}(p_{i - 1}, p_{i}))\right)
Let’s define D(p) as the depth of node p, and F(p) = \sum_{x \text{ on path from root to } p} \texttt{sub\_tree\_size}(x)\times (\texttt{edge\_weight}(\texttt{parent}(x), x))
Then C(T, p_k) = C(T, p_0) + \texttt{size}(T)\times (D(p_k) - D(p_0)) - 2\times (F(p_k) - F(p_0))
This form is exactly suitable for the convex hull trick.
Now, for each sub-tree, we can only use the nodes which belong to it to rejoin to the larger tree, so we need to be careful to not include lines which represent nodes outside the subtree in the CHT envelope.
Note that dfs order gives us a continuous range for each node, which includes all of its descendants.
So we can reduce the problem to range queries where we have to find the minimum over the lines that represent the nodes in the range.
Hence we make a segment tree where in each node we store a vector for the convex hull trick.
Note that there are no updates once the tree is built, the trouble is queries. It is expensive to merge two hulls. Hence, we just query each of the convex hulls in the O(\log N) nodes which represent any arbitrary interval, and take the minimum value of the lot.
This gives an overall run-time of O(N\times log^{2} N).