#P4629. [SHOI2015] 聚变反应炉

[SHOI2015] 聚变反应炉

题目描述

曾经发明了零件组装机的发明家 SHTSC 又公开了他的新发明:聚变反应炉——一种可以产生大量清洁能量的神秘装置。

众所周知,利用核聚变产生的能量有两个难点:一是控制核聚变反应的反应强度,二是使用较少的能量激发聚变反应。而 SHTSC 已经完美解决了第一个问题。一个聚变反应炉由若干个相连的聚变块组成,为了能够使得聚变反应可控,SHTSC 保证任意两个聚能块都可以通过相互之间的链接到达,并且没有一个聚能块可以不重复经过一个链接回到它自己。

但是第二个问题 SHTSC 还没有完全解决。在他设计的聚变反应炉当中,每个聚变块都需要一定的初始能量 did_i 来进行激发,不过 SHTSC 不需要手动激发所有聚变块,这是因为一旦一个聚变块被激发,则会向与其直接相连的所有还未被激发的聚变块传送 cic_i 个单位的能量。这样后被触发的聚变块可以以更低的初始能量来激发,甚至可能不需要额外的外界能量就可自行激发,从而降低了总激发能量的消耗。现在给出了一个聚变反应炉,求至少要多少能量才能激发所有聚变块。

输入格式

第一行一个整数 nn,表示共有 nn 个聚能块,由 11nn 编号。

第二行 nn 个整数,依次表示 did_i

第三行 nn 个整数,依次表示 cic_i

以下 n1n - 1 行每行两个整数 u,vu, v,表示编号为 uuvv 的聚能块是相连的。

输出格式

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

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

提示

Case # max{ci}\max\{c_i\} nn 附加限制
1 =1= 1 10\leq 10 ci=1c_i = 1
2 100\leq 100
3 200\leq 200
4 =0= 0 10\leq 10 -
5 =1= 1 200\leq 200 ci=1c_i = 1
6 -
7 100000\leq 100000 ci=1c_i = 1
8 =0= 0 -
9 =1= 1
10
11 5\leq 5 20\leq 20
12 cic_i 均相等
13 200\leq 200 -
14 cic_i 均相等
15 -
16
17 2000\leq 2000 cic_i 均相等
18 -
19
20

对于所有数据,保证 1di,di1091 \le d_i, \sum d_i \le {10}^9