【深度优先搜索7】小塔的奇妙树

题目简述

小塔有一棵包含 n 个点的树，树的根为 1 号点。每个点有一个权值，树是奇妙树的定义是：任意节点的权值都要大于等于其子节点权值之和。我们的目标是，通过对树中的节点执行最少的加一操作，使得这棵树变成一棵奇妙树。

解题思路

1. 奇妙树的要求

对于每一个节点 u，若该节点有多个子节点 $v1, v2, ..., vk$，则要求：

本题为2024年9月8日字节跳动机考原题

字节跳动机考的介绍点击这里

题目内容

小塔有一棵$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$.