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 $N1$ 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 $reroot$ 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(2N1)$ 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 "rerooting"(at least some of the programmers call it so). Now, we will $reroot$ 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)$:
Now, all we need to do after updating the values is call one of the children and now reroot 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 reroot another one of the children's of $u$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 17 Feb, 17:10
