← 返回题目列表

Codeforces · 1528/A

A. 帕莎的巨大树

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

Parsa 在 $$$n$$$ 个顶点上有一棵巨大的树。

在每个顶点 $$$v$$$ 上,他写了两个整数 $$$l_v$$$ 和 $$$r_v$$$。

为了让Parsa的树看起来更加雄伟,尼玛想给每个顶点$$$v$$$分配一个数字$$$a_v$$$ ($$$l_v \le a_v \le r_v$$$),这样Parsa的树的美感就最大化了。

尼玛的美感有点奇怪。他将树的美丽定义为树的所有边 $$$(u, v)$$$ 上 $$$|a_u - a_v|$$$ 的总和。

由于帕莎的树太大了,尼玛无法独自发挥最大的美丽。你的任务是为帕莎树找到最大可能的美丽。

输入

第一行包含一个整数 $$$t$$$ $$$(1\le t\le 250)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 10^5)$$$ — Parsa 树中的顶点数。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \le l_i \le r_i \le 10^9)$$$。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \le u , v \le n, u\neq v)$$$ 意味着 Parsa 树中的顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。

保证给定的图是一棵树。

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

输出

对于每个测试用例,打印 Parsa 树的最大可能的美感。

示例

输入 #1

3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6

输出 #1

7
8
62

注意

示例中的树:

在第一个测试用例中,一个可能的赋值是 $$$a = \{1, 8\}$$$,其结果是 $$$|1 - 8| = 7$$$。

在第二个测试用例中,可能的分配之一是 $$$a = \{1, 5, 9\}$$$,这会导致 $$$|1 - 5| 的美丽结果。 + |5 - 9| = 8$$$