Can someone help me with this graph problem?

Правка en2, от fck_cheater, 2021-11-02 15:07:06

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:

  1. Make adjacent nodes's stones ​equal to this node's stones

  2. 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский fck_cheater 2021-11-02 15:07:06 229 Tiny change: 'q86194191) can someo' -> 'q86194191). can someo'
en1 Английский fck_cheater 2021-11-02 15:03:32 803 Initial revision (published)