思路:贪心 + 树上dfs
考虑dfs,在自底向上的过程中记录子节点的权值和。
1.如果a[u] < s,至少让a[u] == s,所以ans += s - a[u]
2.如果a[u] >= s,那么u不需要增加权值就能满足条件
代码
题目内容
在一家公司中，员工形成树状的层级结构，编号为 1 到 n，其中 1 号是最高领导。第 i 名员工有一个基础能力值 ai。
我们称这个层级结构是和谐的，当且仅当每一名员工的能力值都不小于其所有直接下属的能力值之和。
每一次训练你可以选择任意一名员工，将其能力值增加 1。请问最少需要多少次训练，才能使整个层级结构变得和谐？
约束条件：
- 员工数量 n 满足 2≤n≤105。
- 能力值 ai 满足 1≤ai≤109。
