题目描述

每次测试的时间限制：3 秒 每次测试的内存限制：512 兆字节

给定一棵包含 $n$ 个节点的树$^{*}$，每个节点 $i$ 有值 $l_i, r_i$。你可以为第 $i$ 个节点选择一个初始值 $a_i$，满足 $l_i \le a_i \le r_i$。如果所有节点的值都相等，则称这棵树是平衡的，平衡树的值定义为任意一个节点的值。

在一次操作中，你可以选择两个节点 $u$ 和 $v$，并将以 $u$ 为整棵树的根时节点 $v$ 的子树$^{\dagger}$ 中所有节点的值增加 $1$。注意 $u$ 和 $v$ 可以相同。

你的目标是通过一系列操作使得树变为平衡的。请找出经过这些操作后树可能达到的最小可能值。注意你不需要最小化操作的次数。

$^{*}$ 树是一个无环的连通图。 $^{\dagger}$ 节点 $w$ 被认为在节点 $v$ 的子树中，如果从根 $u$ 到 $w$ 的任何路径都必须经过 $v$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 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 \ne v_i$）—— 连接 $u_i$ 和 $v_i$ 的边。保证给定的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 经过操作后所有 $a_i$ 能变成相等的最小可能值。可以证明答案总是存在的。

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

11
3
3
5
3000000000
98

注意

在第一个测试用例中，你可以选择 $a = [6,6,0,5]$。

你可以执行以下操作使所有 $a_i$ 相等：

选择 $u = 4$，$v = 3$，执行操作 $5$ 次。

选择 $u = 1$，$v = 3$，执行操作 $6$ 次。

完整的过程如下所示（括号内是 $a$ 的元素）。