CLTRTS - Coders' Legacy 2017A

help
1

Someone please explain me how to approach for this question
LINK: https://www.codechef.com/COLG2017/problems/CLTRTS

2

Hey @k1k4_313, @subham_75 and I were the problem setters for Coders’ Legacy. We will be uploading the editorials within a few days and you can refer to that for a detailed explanation. However I can tell you the approach very briefly for now.

  1. Pick an arbitrary vertex as root.
  2. Run a dfs from this root and for each node collect the maximum value of treats in the subtrees rooted at the children and save them. However a node does not know the how many treats can be collected by going up the parent subtree. The root is the only exception to this, as it has no parent.
  3. So we run a second dfs from the root sending the corresponding maximum value of treats for the parent subtree down to the children. Now each node knows the maximum treats that can be collected by going into each node connected to it.
  4. For each node the answer is the weight at the node + the maximum value of the maximum treats that can be collected by going into each node connected to it.
2 Likes