问题 N: 光棱塔

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:76 解决:2

题目描述

D最近迷上了玩红色警戒,他最喜欢的建筑是光棱塔。

光棱塔是游戏《红色警戒2》中盟军的高级防御武器,由爱因斯坦博士提供光棱科技,墨西哥尤卡坦半岛光棱科技研究中心设计而成,其作用与苏军的磁暴线圈和尤里的心灵控制塔相似。

光棱塔使用的是爱因斯坦发明的光棱技术,由巨大的棱镜构成,其原理是依靠发射类似于激光的光束来打击敌人。

集群的光棱塔要比单台的攻击力增加很多,因为邻近的光棱塔可以进行援助。

这种援助最多可以由多台光棱塔供给,即使是苏军的重坦克也无法抵挡这样强大的攻击。

光棱塔的设计是这样的,为了能够使得光棱反应可控,需要保证任意两个棱镜块都可以通过相互之间的链接到达,并且没有一个棱镜可以不重复经过一个链接回到它自己。

在一群光棱塔当中,每个棱镜都需要一定的初始能量 di来进行激发,不过 我我们不需要手动激发所有棱镜,这是因为一旦一个棱镜被激发,则会向与其直接相连的所有还未被激发的棱镜传送 ci个单位的能量。这样后被触发的棱镜可以以更低的初始能量来激发,甚至可能不需要额外的外界能量就可自行激发,从而降低了总激发能量的消耗。现在给出了一片光棱塔区域,求至少要多少能量才能激发所有光棱塔。

输入

第一行一个整数 n,表示共有 n 个光棱塔,由 1 至 编号。

第二行 n个整数,依次表示 di

第三行 n个整数,依次表示 ci

以下 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

提示

n <= 100000

Ci <= 5

1 <= di , ∑di<=10^9