In the Google Drive architecture, a folder hierarchy is maintained where folders can be nested within one another (folders 1 to n).
Each folder has a specific access level, represented by an integer.
A hierarchy is considered "Synced" when the absolute difference between the access levels of any two directly connected folders (a parent and its child) is at most 1.
Due to a recent update, some folders have had their access levels changed. To maintain security integrity and ensure the hierarchy is "Synced", you must increase the access levels of other folders.
Your goal is to find the minimum total increase in access levels required to make the entire folder hierarchy "Synced".
Note: You can only increase access levels; you cannot decrease them.
Example
Consider the following hierarchy tree:
- Input tree with initial access levels
- Modified tree after the minimum required increases
In the example, the optimal adjustment is to increase folder access levels along the tree so that every parent-child pair differs by at most 1. The total increase is the minimum possible.
The key idea is to enforce the tree constraint that every parent-child pair must differ by at most 1, while only increasing values. A greedy tree traversal can propagate the minimum valid level upward or downward so that each node is raised only when necessary. After the final valid levels are determined, the answer is the sum of all increases over the original access levels. This is a tree-greedy / DFS style problem focused on constraint propagation and minimizing total increments.
