← 返回题目列表

Codeforces · 2062/D

D. 平衡树

中文机器翻译题面 查看原题

给定一棵树$$$^{\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$$$的元素):

可以证明这是最优解。