Byteasar's Delivery Optimization

In the village of Byteville, there are \(n\) houses connected by \(n-1\) roads forming a tree. Each pair of houses is connected by a unique path. House 1 belongs to Byteasar, the village administrator, who has \(n\) computers at his disposal. He must deliver one computer to every house along a route starting and ending at his own house. The twist is that as soon as a house receives its computer, the residents immediately start installing the game FarmCraft. The installation time for each house differs and is known in advance.

Byteasar has just enough gasoline to drive each road twice, so the total travel time along the roads is fixed at \(2(n-1)\) minutes (each road takes 1 minute to traverse). However, the order in which he delivers the computers influences the time at which each house can start playing.

For any house \(u\) (other than 1), if the computer is delivered at time \(d_u\) and the installation time is \(a_u\), then the house will be ready at time \(d_u + a_u\). After delivering to all other houses, Byteasar returns to house 1 and only then installs FarmCraft, so his ready time is \(T_{total} + a_1\) where \(T_{total}\) is the total travel time. The objective is to plan a delivery order (a valid Eulerian trail on the tree) which minimizes the maximum ready time across all houses.

Hint: Since the total travel time is fixed, the key is to deliver computers to houses with longer installation times as early as possible. A greedy strategy that, at each house, visits the children (neighbors not yet visited) in descending order of their installation times, works well in practice.

Formally, if:

• \(d_u\) denotes the time when house \(u\) gets its computer (i.e. the first time Byteasar visits house \(u\)),
• \(a_u\) is the installation time of house \(u\),
• The final delivery route (an Eulerian trail) takes \(2(n-1)\) minutes, and Byteasar installs at house 1 after returning,

then the goal is to determine a route minimizing

[ T = \max \Big{\max_{u \neq 1} (d_u + a_u),; 2(n-1) + a_1 \Big}. ]

Your task is to compute the minimal possible \(T\) for a given tree and installation times, assuming Byteasar follows the optimal delivery order as described.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq 2\times10^5\)), the number of houses.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \leq u,v \leq n\)) indicating that there is a bidirectional road between house \(u\) and house \(v\).

The last line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) (\(0 \leq a_i \leq 10^9\)) is the installation time at house \(i\). Note that house 1 is Byteasar's house.

outputFormat

Output a single integer \(T\), the minimal time by which all houses (including Byteasar's) have FarmCraft installed, if Byteasar follows an optimal delivery order.

sample

4
1 2
1 3
3 4
4 5 2 3

9

</p>