You are not logged in. Please login at www.codechef.com to post your questions!

×

BIGFIGHT Editorial

0
1

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.

This question is marked "community wiki".

asked 17 Feb, 17:10

kamal1998's gravatar image

4★kamal1998
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,214
×1,236
×711

question asked: 17 Feb, 17:10

question was seen: 151 times

last updated: 17 Feb, 17:10