Capturing a country

Ant and Bob two army want to capture a country. The country is consist of N cities. To capture the city i, it takes Ant A_[i] minutes, and Bob needs B_[i] minutes to capture city i. Due to the similarity of neighboring cities, If the city i and j are neighboring cities, if Ant has captured city i, then the time for Ant to capture city j is A_[j]/2. Of course if Ant has captured city j, then the time for Ant to capture city i is A_[i]/2. It is the same for Bob. We define the total time to capture a country be the time to capture city 1 + the time to capture city 2 + ... + the time to capture city N. Now we want to know the minimal total time.
For simplicity, we assume that there is only one path to go from one city to another city.

The first line contains a integer N(0<N<100), which is the number of cities.Then following N lines describe A_[1], A_[2], …, A_[N];Then following N lines describe B_[1], B_[2], …, B_[N];Next comes N-1 lines, each contains two integers x, y, meaning that city x and city y are neighboring.

Just output the minimal total time in a single line.

3
1 2 5
3 8 1
1 2
1 3

3

HIT

2012 Multi-University Training Contest 5