P14341.【深度优先搜索7】小塔的奇妙树
本题为2024年9月8日字节跳动机考原题
字节跳动机考的介绍点击这里
题目内容
小塔有一棵n个点的树，其中1号点是根。每个点有一个权值ai。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。
小塔每次操作可以选择一个点，将其权值加一。请问小塔最少需要多少次操作，才能使这棵树变成一棵奇妙树。
输入描述
第一行一个整数n，表示树的节点数。
第二行n 个整数ai;，表示每个点的权值。
接下来n−1行，每行两个整数u和v，表示u和v之间有一条边。
2≤n≤105
1≤ai≤109
1≤u,v≤n
输出描述
输出一个整数，表示最少需要多少次操作。
样例1
输入
3
1 2 3
1 2
1 3
输出
4
说明
至少需要4次操作，将1号点的权值变为5.
