#P2027. 2024.9.8-ZJTD-第3题-小塔的奇妙树

2024.9.8-ZJTD-第3题-小塔的奇妙树

题目内容

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

输入描述

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

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

接下来n−1n-1行，每行两个整数uu和vv，表示uu和vv之间有一条边。

2≤n≤1052≤n≤10^5

1≤ai≤1091≤a_i≤10^9

1≤u,v≤n1≤u,v≤n

输出描述

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

样例1

输入

 3
 1 2 3

输出

4

说明

至少需要44次操作，将11号点的权值变为55.

知识点:*****

查看知识点以及同类型题目

Statistics