PROBLEM LINK:
Author: manjunath1996
Editorialist: neeladree
DIFFICULTY:
EASY
PREREQUISITES:
Depth First Search
PROBLEM:
A tree is given. Each vertex has a number n associated with it. The value of a node is equal to the sum of its number and value of its parent calculated recursively. Calculate the sum of value of all the nodes in the tree.
QUICK EXPLANATION:
Update all the node values in an array while processing the queries. After, that update the weights of all the nodes with dfs.
EXPLANATION:
Since, all the people can go from their city to only their parent city, therefore, only those people will be able to watch a concert which are in the subtree of the city Harsh is currently visiting. So, the sum a person hears will be the sum of the lucky numbers of all its ancestor cities.
While processing the queries, update the value of individual node with each query. Do not try to update the subtree nodes at the time. It will lead to TLE. After that, with a single DFS, update the value of all the nodes while moving down a subtree.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.