8593: BZOJ4593：[Shoi2015]聚变反应炉

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

输入格式

第一行一个整数n。表示共有n个聚能块，由1-n编号。 第二行n个整数，表示di。 第三行n个整数，表示ci。 以下n-1行每行两个整数，u，v。表示编号为u和v的聚能块是相连的。 输入保证符合题目描述。 Type A ：ci <= 1,有 n<=100000。 Type B ：ci <= 5,有n<=2000。 对于所有的数据，1<=di, Sum(di)<=10^9。输入保证符合题目描述。

输出格式

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

样例输入

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

样例输出

1
//样例1：只需要触发任意一个聚变块即可激活整个聚变反应装置。

提示

没有写明提示

题目来源

By 佚名上传