# 描述

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.

## Input

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$.

## Output

For each test case, print a single line containing an integer, denoting the minimum initial HP.

# 思路

• 在不考虑树的偏序限制的情况下，就是经典的流水线调度贪心。使用Johnson法则排序即可。
• 考虑原问题，先求出忽略父亲限制的最优攻击顺序：$p_1, p_2, p_3, \ldots, p_n$。
• 若$p_1$是树根，则第一步打$p_1$一定最优；
• 否则，在打完$p_1$的父亲$x$之后接着打$p_1$一定最优。
把$p_1$和$x$两只怪兽合并为一只，并将$p_1$的所有儿子的父亲改为$x$。
• 这样就可以规模为$n$的问题变成$n - 1$的问题，重复上述操作直到只剩下一个怪兽。
• 用堆来维护最优怪兽，并查集维护父亲即可。具体实现见代码。

0%