Given a rooted tree consisting of n nodes numbered from 1 to n where each node has some number of stones on it represented by the array stones, modify this tree by placing any number of stones on node any number of times.
Now We've to modify the tree such that absolute difference between the number of stones between each pair of adjacent nodes is less than or equal to 1. We've to find the minimum number of extra stones such that this is true.
My approach(Tled): We start from node having maximum number of stones and from there we make two calls in dfs as follows:
Make adjacent nodes's stones equal to this node's stones
Make adjacent nodes's stones equal to this node's stones-1
Constraints: 1<=n<=1e5
I assure you that it's not from ongoing contest because it's here. can someone give any idea?
Comments (0)
