思路:贪心 + 树上dfs

考虑dfs,在自底向上的过程中记录子节点的权值和。

1.如果a[u] < s,至少让a[u] == s,所以ans += s - a[u]

2.如果a[u] >= s,那么u不需要增加权值就能满足条件

代码

题目内容

小红有一棵$n$个点的树，其中$1$号点是根。每个点有一个权值$a_i$。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。 小红每次操作可以选择一个点，将其权值加一。请问小红最少需要多少次操作，才能使这棵树变成一棵奇妙树。

输入描述

第一行一个整数$n$，表示树的节点数。

第二行n 个整数$a_i$;，表示每个点的权值。

接下来$n-1$行，每行两个整数$u$和$v$，表示$u$和$v$之间有一条边。

$2≤n≤10^5$

$1≤a_i≤10^9$

$1≤u,v≤n$

输出描述

输出一个整数，表示最少需要多少次操作。

样例1

输入

3
1 2 3
1 2
1 3

输出

4

说明

至少需要$4$次操作，将$1$号点的权值变为$5$.