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