Parsa 的大树

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一棵有 $n$ 个顶点的树。每个顶点 $v$ 有两个整数 $l_v,r_v$。你需要为每个顶点选择一个 $a_v$，满足 $l_v\le a_v\le r_v$。

树的美丽值定义为所有边 $(u,v)$ 上 $|a_u-a_v|$ 的总和。求美丽值的最大可能值。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$。接下来 $n$ 行，第 $i$ 行包含 $l_i,r_i$。 随后 $n-1$ 行每行包含两个整数 $u,v$，表示一条树边。

输出格式

对每个测试用例输出一行一个整数，表示最大美丽值。

样例输入 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

数据范围

$1\le t\le250$，$2\le n\le10^5$，$1\le l_i\le r_i\le10^9$；保证输入图是一棵树， 且所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。