题目背景

荧晶是蓝晶星球上一种蕴藏巨大能量的神秘矿物,如何运输和储存它一直是星球的头号难题。

题目描述

蓝晶星球上有 $N$ 座城市,编号 $1$ 到 $N$,其中 $1$ 号是首都。$N$ 座城市由 $N-1$ 条单向高速通道相连,构成一棵以 $1$ 号城市为根的树,通道方向由儿子指向父亲。树按深度分层:根深度为 $0$,属于第 $1$ 层;根的子结点深度为 $1$,属于第 $2$ 层;以此类推,深度为 $i$ 的结点属于第 $i+1$ 层。

每座城市建有一座容量为 $A_i$ 的荧晶储存器。储存器除储存外还有自动采集功能:晚上六点时若某储存器未满,它会自动采集空气中的荧晶能量,并在早上六点前采满;但只有完全空的储存器启动采集程序才是安全的。

每天早上六点到七点,首都(根结点)储存器中的荧晶被消耗殆尽;首都不会自动采集,只接受子结点传来的荧晶。早上七点起,城市之间逐层传输:先由第 $2$ 层向第 $1$ 层传输,直到第 $1$ 层储存器满或第 $2$ 层储存器全空;再由第 $3$ 层向第 $2$ 层传输,直到第 $2$ 层每个结点的储存器满或其子结点(第 $3$ 层)全空;依此类推,直到最后一层。传输总能在晚上六点前完成。

由于技术原因,运输方案必须满足:

1. 任何储存器到晚上六点传输结束时,不能处于非空又未满的状态(否则会对存有荧晶的储存器启动采集程序,引发危险),即必须要么空、要么满;

2. 首都的储存器每天早上六点到七点间会自动清空,方案无需考虑首都的荧晶如何运走;

3. 除首都外,每座城市必须在子结点向它运输之前,把自身储存器中原有的荧晶全部运给父结点,不允许残留荧晶与外来荧晶混合;

4. 运往同一座城市的若干来源的荧晶数量必须完全相同,否则不同来源的荧晶按不同比例混合可能发生危险。

现在通道已建好,每座城市也有了给定容量的储存器。为满足上述限制,可能需要重建一些城市的储存器:你可以(也只能)摧毁某几座城市(含首都)原有的储存器,并新建容量为任意正实数(原始容量为正整数,重建后可以是小数)的新储存器。求最少需要重建的储存器数目。

形式化题面:给定一棵 $n$ 个结点的树,每个点有正整数权值 $a_i$。称权值方案 $w$ 是好的,当且仅当:对所有非叶结点 $u$,$u$ 的所有儿子的 $w_v$ 相等,且这些儿子的 $w_v$ 之和等于 $w_u$。你可以把 $a_i$ 修改为任意正实数,求最小的修改个数。

输入格式

第一行一个正整数 $N$,表示城市数目。

接下来 $N$ 行,每行一个正整数,第 $i$ 行表示第 $i$ 座城市原有储存器的容量。

最后 $N-1$ 行,每行两个正整数 $a, b$,表示城市 $b$ 到城市 $a$ 有一条高速通道($a \neq b$)。

输出格式

输出一行一个整数,表示最少需要重建(即修改容量)的储存器数目。

样例

5
5
4
3
2
1
1 2
1 3
2 4
2 5

3

提示

样例解释:一个最优解是把 $A_1$ 改成 $8$,$A_3$ 改成 $4$,$A_5$ 改成 $2$。这样 $2$ 和 $3$ 运给 $1$ 的量相等,$4$ 和 $5$ 运给 $2$ 的量相等,且晚上六点时 $1$、$2$ 满,$3$、$4$、$5$ 空,满足所有限制。

对于 $100\%$ 的数据,$N \lt 500000$,$A_j \lt 10^8$。