P15751 [JAG 2024 Summer Camp #3] Fragile Tree

In the ICPC Park, there is a giant tree where a group of squirrels has made their nests. The squirrels' nests consist of $N$ rooms numbered $1, 2, \ldots, N$ and $N - 1$ bidirectional roads numbered $1, 2, \ldots, N - 1$ that connect the rooms. It is guaranteed that any two rooms can be reached from each other by following the roads. Room $1$ is the gathering place for the group, while the other rooms serve as sleeping quarters. Each room $i$ has $a_i$ squirrels living in it, where $a_1 = 0$. Now, the squirrels are trying to gather in Room $1$ for a morning assembly by following the roads from their sleeping quarters. However, due to a severe storm last night, each road has become fragile, and the $i$-th road can only allow up to $c_i$ squirrels to pass through before it collapses. As an animal lover, your task is to choose one road to reinforce in order to maximize the number of squirrels that can reach Room $1$. The reinforced road will not collapse, no matter how many squirrels pass through it.

The input consists of a single test case of the following format. $$\begin{aligned} &N \\ &a_1 \ a_2 \ \ldots \ a_N \\ &u_1 \ v_1 \ c_1 \\ &u_2 \ v_2 \ c_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \ c_{N-1} \end{aligned}$$ The first line consists of an integer $N$ between $2$ and $200,000$, inclusive. The second line contains $N$ non-negative integers $a_1, a_2, \ldots, a_N$. The integer $a_i$ denotes the number of squirrels living in Room $i$, with $a_1 = 0$ and $0 \leq a_i \leq 10^9$ ($i = 2, 3, \ldots, N$). Each of the following $N - 1$ lines contains three integers $u_i$, $v_i$ and $c_i$ ($1 \leq u_i, v_i \leq N$, $0 \leq c_i \leq 10^9$). $u_i$ and $v_i$ denote the endpoints of the $i$-th road, and $c_i$ denotes its durability. It is guaranteed that the given graph is a tree.

Print the maximum number of squirrels that can reach Room $1$.