CF1528A Parsa's Humongous Tree

Parsa 有一棵有 $n$ 个点的巨大树。 在每个顶点 $v$ 上，他写下了两个整数 $l_v$ 和 $r_v$。 为了让 Parsa 的树看起来更加壮观，Nima 想要为每个顶点 $v$ 分配一个数 $a_v$（满足 $l_v \le a_v \le r_v$），使得 Parsa 的树的美丽值最大。 Nima 对美丽的定义非常奇特。他将树的美丽值定义为所有树边 $(u, v)$ 的 $|a_u - a_v|$ 之和。 由于 Parsa 的树太大了，Nima 无法独自最大化它的美丽值。你的任务是求出 Parsa 的树的最大可能美丽值。

第一行包含一个整数 $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$），表示树中存在一条连接顶点 $u$ 和 $v$ 的边。 保证给定的图是一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 Parsa 的树的最大可能美丽值。

示例中的树如下：  在第一个测试用例中，一种可能的分配是 $a = \{1, 8\}$，此时美丽值为 $|1 - 8| = 7$。 在第二个测试用例中，一种可能的分配是 $a = \{1, 5, 9\}$，此时美丽值为 $|1 - 5| + |5 - 9| = 8$。 由 ChatGPT 4.1 翻译