22696_TombRaider

Known as a famous twentieth-century tomb raider, Lara now has a new target: one of the Egypt king's Pyramid which is supposed to abound with all kinds of treasures, shown in Figure 1. In order to make her plan perfect and reduce the risk she faces, she has stolen a map and some documents of the Pyramid in the Ancient Culture Museum (ACM).

Figure 1  Map of the Pyramid

According to the map of the Pyramid above, she has observed that the inner Pyramid consists of several chambers which are connected by tunnels. Explicitly, the topmost chamber is called the King's Chamber from which one can reach any other chamber by moving downwards through the tunnels. Moreover, the path from the King’s Chamber to any other chamber is unique.

All the treasures are stored in the chambers. The chambers are labeled by consecutive integers starting from 1. Now, the problem obfuscating Lara is that the exact value of the treasure in each chamber is still unknown. Actually, Lara has found a list about the value of treasures each chamber contains from the old documents. But the Chamber Label part of the list is unfortunately broken by bookworms (As Figure 2 shows). In another word, Lara knows all the treasure values of the chambers but she does not know which chamber each value should be corresponded to.

After a short research on other documents, Lara discovers some rules followed by the ancient people while they were storing the treasures. But first of all, two technical terms must be introduced: Sub-Chambers and Direct-Sub-Chambers. A chamber's Sub-Chambers are a set of chambers that can be reached from this chamber by moving downward through the tunnels. For example, in Figure 1, Chamber 2's Sub-Chambers are Chamber 4, 5, 6 and 7. A chamber's Direct-Sub-Chambers are a set of chambers that can be reached from this chamber by moving downward through exactly one tunnel. For example, in Figure 2, Chamber 2's Direct Sub-Chambers are Chamber 4 and Chamber 5.

Figure 2  Chamber Treasure Value

Here are the rules:

1. From another document, you can find a list giving each chamber a value S(i), which means there are S(i) chambers in Chamber Vs Sub-Chambers that have less treasure than Chamber i.

2. If a chamber has Direct-Sub-Chambers labeled i and j, assuming i < j, then any chamber of Chamber i and Chamber i's Sub-Chambers has less treasure than any chamber of Chamber j and Chamber j's Sub-Chambers.

According to the data (the list of S(i) and the set of treasure values) and the rules above, you have sufficient information to tell each chamber how much treasure it contains. To prevent the tomb raiders from stealing the treasures, the designer of the Pyramid made the traps that once a person goes through the tunnel, the stone door in the middle of the tunnel will be shut down forever. So each tunnel can be traveled only once. Lara wants to get as much treasure as possible by selecting the proper starting chamber and ending chamber.

There are several test cases in the input file. Each case consists of three parts.

The first part is formed by an integer n and n-1 pairs of integers following, n is the number of the chambers within the Pyramid. Then the n-1 pairs describe the n-1 tunnels. The first integer of each pair is the label of the upper chamber of the tunnel and the second integer is the lower chamber. Note, 2 ≤ n ≤ 10000.

The second part consists of n integers, one line each, indicating the set of chamber treasure values. Each integer ranges from 0 to 100 000. All these integers are distinct.

The third part consists of n integers, one line each. The i-th integer is the value S(i) of the Chamber i.

Output an integer in a single line, denoting the maximum treasure value Lara can get.

7
1 3
1 2
2 4
2 5
4 7
4 6
1500
2312
1314
517
892
1039
2445
3
1
0
1
0
0
0

7190

The solution of the sample is shown in Figure 3.

Figure 3  The Solution