Thieves' Guild
Limits: 3 sec., 512 MiB
This statement was translated automatically from Ukrainian. In case of any discrepancy, the Ukrainian version is authoritative.
In a certain kingdom, there are \(n\) cities connected by \(n-1\) roads such that it is possible to reach any pair of cities via the roads. In other words, the cities and roads form a tree.
In each city, there is a bank, and the bank vault in city \(v\) contains \(a_v\) coins. In one of the cities, a thieves’ guild has originated, planning to rob the banks of the entire kingdom. Unfortunately, the king does not know in which exact city this happened, so to prevent a massive heist, he decided to make all the roads of the kingdom directed, despite the fact that after this, it will no longer be possible to reach any city from any other city.
Yet, the robbery will take place! The guild will rob all banks in all cities that can be reached from the city where the guild originated.
Since the king wants to choose such road directions to minimize the maximum possible damage. More formally, let \(c_v\) be the sum of the number of coins in all cities that are reachable from city \(v\) after the king chooses the direction of each road (including city \(v\)). Then you need to choose the directions so as to minimize \(\max c_v\).
Input
The first line contains a single integer \(n\) – the number of cities in the kingdom.
The next line contains \(n\) integers \(a_i\) – the number of coins in the banks.
The \(i\)-th of the following \(n-1\) lines contains two integers \(u_i\) and \(v_i\), meaning there is a road between the cities with these numbers.
Output
Output a single number – the minimum possible value of \(\max c_v\).
Constraints
\(2 \le n \le 10^5\),
\(1 \le a_i \le 10^9\),
\(1 \le u_i, v_i \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 1 2 3 4 5 6 7 1 2 1 3 2 4 2 5 4 6 1 7 | 12 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 4 6 1 7 | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 4 7 1 2 | 11 |
Notes
In the first example, vertex \(v\) contains \(v\) coins. A possible edge orientation is shown in the figure. Then if the guild is located at vertex 2, they can rob the bank in vertices 1, 2, 4, and 5. \(c_2 = a_1 + a_2 + a_4 + a_5 = 12\). For all other vertices, this value is smaller.
In the second example, each vertex has one coin. One of the ways to orient the edges:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|