[SHOI2015] 聚变反应炉

曾经发明了零件组装机的发明家 SHTSC 又公开了他的新发明：聚变反应炉——一种可以产生大量清洁能量的神秘装置。 众所周知，利用核聚变产生的能量有两个难点：一是控制核聚变反应的反应强度，二是使用较少的能量激发聚变反应。而 SHTSC 已经完美解决了第一个问题。一个聚变反应炉由若干个相连的聚变块组成，为了能够使得聚变反应可控，SHTSC 保证任意两个聚能块都可以通过相互之间的链接到达，并且没有一个聚能块可以不重复经过一个链接回到它自己。 但是第二个问题 SHTSC 还没有完全解决。在他设计的聚变反应炉当中，每个聚变块都需要一定的初始能量 $d_i$ 来进行激发，不过 SHTSC 不需要手动激发所有聚变块，这是因为一旦一个聚变块被激发，则会向与其直接相连的所有还未被激发的聚变块传送 $c_i$ 个单位的能量。这样后被触发的聚变块可以以更低的初始能量来激发，甚至可能不需要额外的外界能量就可自行激发，从而降低了总激发能量的消耗。现在给出了一个聚变反应炉，求至少要多少能量才能激发所有聚变块。

第一行一个整数 $n$，表示共有 $n$ 个聚能块，由 $1$ 至 $n$ 编号。 第二行 $n$ 个整数，依次表示 $d_i$。 第三行 $n$ 个整数，依次表示 $c_i$。 以下 $n - 1$ 行每行两个整数 $u, v$，表示编号为 $u$ 和 $v$ 的聚能块是相连的。

一行一个整数，表示至少需要多少个单位的能量才能激发所有聚变块。

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

1

| Case # | $\max\{c_i\}$ | $n$ | 附加限制 | |:---:|:---:|:---:|:---:| | 1 | $= 1$ | $\leq 10$ | $c_i = 1$ | | 2 | $= 1$ | $\leq 100$ | $c_i = 1$ | | 3 | $= 1$ | $\leq 200$ | $c_i = 1$ | | 4 | $= 0$ | $\leq 10$ | - | | 5 | $= 1$ | $\leq 200$ | $c_i = 1$ | | 6 | $= 1$ | $\leq 200$ | - | | 7 | $= 1$ | $\leq 100000$ | $c_i = 1$ | | 8 | $= 0$ | $\leq 100000$ | - | | 9 | $= 1$ | $\leq 100000$ | - | | 10 | $= 1$ | $\leq 100000$ | - | | 11 | $\leq 5$ | $\leq 20$ | - | | 12 | $\leq 5$ | $\leq 20$ | $c_i$ 均相等 | | 13 | $\leq 5$ | $\leq 200$ | - | | 14 | $\leq 5$ | $\leq 200$ | $c_i$ 均相等 | | 15 | $\leq 5$ | $\leq 200$ | - | | 16 | $\leq 5$ | $\leq 200$ | - | | 17 | $\leq 5$ | $\leq 2000$ | $c_i$ 均相等 | | 18 | $\leq 5$ | $\leq 2000$ | - | | 19 | $\leq 5$ | $\leq 2000$ | - | | 20 | $\leq 5$ | $\leq 2000$ | - | 对于所有数据，保证 $1 \le d_i, \sum d_i \le {10}^9$。