Problem D: 直北关山金鼓振

Problem D: 直北关山金鼓振

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 18  Solved: 1
[Submit][Status][Web Board]

Description

李将军虽然没有叶书生那么荣华富贵,但是确实是一位保家卫国的好将军,他曾经火速平定了渔阳的叛乱,你的历史书上说这至少使大唐的繁荣往后延续了三百年。

在渔阳山丘中,隐藏着n个村落。通过若干条道路相连。目前你军队面前的是村落1,你必须先攻占村落1

我们的摸金校尉重金买通了村落的平民,现在知道村落中有N-1条单向道路相连,这些道路不存在环,所有的N个村落都可以通过给出的道路到达。

李将军手下有充足的兵力,如果结点x被攻占,与结点x相连的且未被攻占的y即可被攻占。

两军对垒,不需要厮杀,李将军只需要穿价格为jk[i]*lol[i]的女装即可迷倒据点i中的所有敌军,兵不血刃的拿下村落,jk[i]为据点i具有的正整数常数,lol[i]为据点i被攻占的顺序,即据点i是第lol个被攻占的。

当然,穿已经穿过的女装敌军是不买账的,所以每到一个村落,他都需要重新购买女装。

李将军想直到他最少需要买多少钱的女装才能迷倒所有的敌军。

Input

输入仅一组数据

对于每一组数据,第一行包含一个整数n1<=n<=5000),其中n是村落的个数。

第二行包含n个整数,其中第ijk[i]1<=jk[i]<=500),是据点i具有的正整数常数。

接下来的n-1行中的每一行都包含两个间隔的村落编号v1v2,它们是道路的两个端点,表示v1能到达v2。没有道路将被列出两次。

Output

对于每一组数据,输出仅一行,表示李将军最少需要花费的金钱。

Sample Input

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

Sample Output

33

HINT

[Submit][Status]