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.
这道题的核心是把整棵树上的访问级别调整到满足“父子节点差值不超过 1”，而且只能做增加不能减少，所以每个节点最终值一定不小于原值，并且还要满足它不小于子节点最终值减 1。最有效的做法是先把树建成邻接表，再从根向下或从叶向上做一次约束传播：当父节点数值不足以覆盖子节点要求时，就把父节点抬高到子节点值减 1 的最小合法位置。由于每次只会增加，最终可以累加所有节点的新旧差值作为答案。这个题本质上是树上的贪心 / DFS（或结合优先队列的传播）问题，关键在于正确处理层级约束并保证总增量最小。
