#1550. aaaaaa
aaaaaa
当前没有测试数据。
题目描述
曾经发明了零件组装机的发明家 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 的聚能块是相连的。
输出格式
一行一个整数,表示至少需要多少个单位的能量才能激发所有聚变块。
样例
数据范围与提示
Case # | \max\{c_i\} | n | 附加限制 |
---|---|---|---|
1 | = 1 | \leq 10 | c_i = 1 |
2 | \leq 100 | ||
3 | \leq 200 | ||
4 | = 0 | \leq 10 | - |
5 | = 1 | \leq 200 | c_i = 1 |
6 | - | ||
7 | \leq 100000 | c_i = 1 | |
8 | = 0 | - | |
9 | = 1 | ||
10 | |||
11 | \leq 5 | \leq 20 | |
12 | c_i 均相等 | ||
13 | \leq 200 | - | |
14 | c_i 均相等 | ||
15 | - | ||
16 | |||
17 | \leq 2000 | c_i 均相等 | |
18 | - | ||
19 | |||
20 |
对于所有数据,保证 1\le d_i,\sum d_i\le 10^9。