给定一棵树$$$^{\text{*}}$$$,其中包含 $$$n$$$ 个节点,每个节点的值为 $$$l_i, r_i$$$。您可以为第$$$i$$$个节点选择一个满足$$$l_i\le a_i\le r_i$$$的初始值$$$a_i$$$。如果所有节点值都相等,则树是平衡树,并且平衡树的值定义为任何节点的值。
在一次操作中,可以选择两个节点$$$u$$$和$$$v$$$,并将节点$$$v$$$的子树$$$^{\text{†}}$$$的值增加$$$1$$$,同时将$$$u$$$作为整棵树的根。请注意,$$$u$$$ 可能等于$$$v$$$。
您的目标是执行一系列操作以使树变得平衡。执行这些操作后找到树的最小可能值。请注意,您不需要最小化操作数量。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 输入测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 树中的节点数。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含两个整数 $$$l_i,r_i$$$ ($$$0\le l_i \le r_i\le 10^9$$$) — 第 $$$i$$$ 节点值的约束。
接下来的 $$$n-1$$$ 行包含树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — 连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 执行操作后所有 $$$a_i$$$ 可以等于的最小可能值。可以证明答案总是存在的。
示例
输入 #1
6 4 0 11 6 6 0 0 5 5 2 1 3 1 4 3 7 1 1 0 5 0 5 2 2 2 2 2 2 2 2 1 2 1 3 2 4 2 5 3 6 3 7 4 1 1 1 1 1 1 0 0 1 4 2 4 3 4 7 0 20 0 20 0 20 0 20 3 3 4 4 5 5 1 2 1 3 1 4 2 5 3 6 4 7 5 1000000000 1000000000 0 0 1000000000 1000000000 0 0 1000000000 1000000000 3 2 2 1 1 4 4 5 6 21 88 57 81 98 99 61 76 15 50 23 67 2 1 3 2 4 3 5 3 6 4
输出 #1
11 3 3 5 3000000000 98
注意
在第一个测试用例中,您可以选择$$$a=[6,6,0,5]$$$。
您可以执行以下操作使所有 $$$a_i$$$ 相等:
1. 选择$$$u=4$$$, $$$v=3$$$ 并执行操作$$$5$$$ 次。
2. 选择$$$u=1$$$, $$$v=3$$$ 并执行操作$$$6$$$ 次。
完整流程如下(括号内的数字为$$$a$$$的元素):
可以证明这是最优解。