Little Q is fighting against scary monsters in the game “Monster Hunter”. The battlefield consists of $n$ intersections, labeled by $1,2,…,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.
The first line of the input contains an integer $T(1\leq T\leq2000)$, denoting the number of test cases.\par
In each test case, there is one integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of intersections.
For the next $n-1$ lines, each line contains two integers $a_i,b_i(0\leq a_i,b_i\leq 10^9)$, describing monsters at the $2,3,…,n$-th intersection.
For the next $n-1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional road between the $u$-th intersection and the $v$-th intersection.
It is guaranteed that $\sum n\leq 10^6$.
For each test case, print a single line containing an integer, denoting the minimum initial HP.
- 考虑原问题，先求出忽略父亲限制的最优攻击顺序：$p_1, p_2, p_3, \ldots, p_n$。
- 这样就可以规模为$n$的问题变成$n - 1$的问题，重复上述操作直到只剩下一个怪兽。