CF1528A.Parsa's Humongous Tree

Parsa has a humongous tree on $n$ vertices.

On each vertex $v$ he has written two integers $l_v$ and $r_v$.

To make Parsa's tree look even more majestic, Nima wants to assign a number $a_v$ ($l_v \le a_v \le r_v$) to each vertex $v$ such that the beauty of Parsa's tree is maximized.

Nima's sense of the beauty is rather bizarre. He defines the beauty of the tree as the sum of $|a_u - a_v|$ over all edges $(u, v)$ of the tree.

Since Parsa's tree is too large, Nima can't maximize its beauty on his own. Your task is to find the maximum possible beauty for Parsa's tree.

帕尔萨有一棵包含 $n$ 个顶点的巨型树。

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

为了让帕尔萨的树看起来更加雄伟，尼马希望为每个顶点 $v$ 分配一个数 $a_v$（满足 $l_v \le a_v \le r_v$），使得帕尔萨的树的“美观度”最大化。

尼马对“美观度”的定义颇为奇特：他将树的美观度定义为树中所有边 $(u, v)$ 对应的 $|a_u - a_v|$ 的总和。

由于帕尔萨的树规模过于庞大，尼马无法独自将其美观度最大化。你的任务是求出帕尔萨的树所能达到的最大美观度。

The first line contains an integer $t$ $(1\le t\le 250)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(2\le n\le 10^5)$ — the number of vertices in Parsa's tree.

The $i$-th of the following $n$ lines contains two integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le 10^9)$.

Each of the next $n-1$ lines contains two integers $u$ and $v$ $(1 \le u , v \le n, u\neq v)$ meaning that there is an edge between the vertices $u$ and $v$ in Parsa's tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case print the maximum possible beauty for Parsa's tree.

对于每个测试用例，输出帕尔萨的树所能达到的最大美观度。

The trees in the example:

In the first test case, one possible assignment is $a = {1, 8}$ which results in $|1 - 8| = 7$.

In the second test case, one of the possible assignments is $a = {1, 5, 9}$ which results in a beauty of $|1 - 5| + |5 - 9| = 8$

示例中的树：

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

在第二个测试用例中，一种可能的赋值方案是 $a = {1, 5, 9}$，其美观度为 $|1 - 5| + |5 - 9| = 8$。