PROBLEM LINK:
https://www.codechef.com/CYRY2019/problems/BIGFIGHT
Author: cypher101
Editorialist: kamal1998
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graph, Trees, Simple Path, DP, DFS
PROBLEM:
You are given a tree with N nodes and N-1 edges and you have been given cost c_i for each node i. For each query your are given two nodes a and b and you have to tell which one of them has the minimal cost. Cost for a node v is defined as \sum_{i=1}^N dist(i,v).c_i where dist(i,v) is the simple path from node i to v.
QUICK EXPLANATION:
The tree is not rooted at the beginning so,let’s first root it at 1 using DFS and calculated the cost for this node let it be res, also let’s keep an array sum where sum_i tells the total of c_i in its subtree for each node i.
Now, all left is to call another DFS and re-root the tree at different nodes and store the cost for each node by manipulating the value of res and the sum array.
As there are only two DFS calls each having complexity O(V+E) and each query can be answered in O(1). Therefore, the overall complexity of the solution would be O(2N-1) that would be O(N).
EXPLANATION:
First lets root the tree at node 1 by using DFS and calculate the cost for this node and lets call it res, just calculate res from the formula given in the problem statement. Also, let’s calculate the sum of cost for each subtree and store it in an array named sum where sum_i tells the total sum of cost of nodes in it’s subtree.
And now comes the part which will stop us from traversing the tree again and again, so let’s apply a technique known as “re-rooting”(at least some of the programmers call it so). Now, we will re-root the tree but without starting DFS all over we can achieve this by maintaining correct values while traversing the tree. So, let’s see how will the values change when we move from node u to v through the edge (u,v):
- Firstly, it can be seen that res will decrease by sum_v (because the distance to each vertex in this subtree will decrease by one).
- sum_u will decrease by sum_v (because node u is no longer the root of the tree and so we must remove this subtree).
- res will increase by sum_u(because the distance to each vertex in this vertex will increase by one).
- sum_v will increase by sum_u (because subtree of node u is now part of subtree of node v).
Now, all we need to do after updating the values is call one of the children and now re-root it and calculate it’s cost and store it. After the DFS call finishes for node v we must reverse the above mentioned steps so, that we can re-root another one of the children’s of u.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.