UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4593. [Shoi2015]聚变反应炉

统计 下载数据

Description

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

Input

第一行一个整数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。输入保证符合题目描述。

Output

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

Sample Input

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

Sample Output

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

Hint

Source

By 佚名上传