g6-07638. 区间取值·相邻差之和最大 未做

改编自 Codeforces 1528A（题面重写、数据自造；原题 URL：https://codeforces.com/problemset/problem/1528/A）

给定 $t$ 组测试数据。每组：一棵 $n$ 个结点的树，每个结点给出区间 $[l_i,r_i]$，需给每个结点选一个整数 $a_i\in [l_i,r_i]$，使 ${\sum }_{(u,v)\in 边}|a_u-a_v|$ 最大。

输入格式：第一行 $t$；每组：第一行 $n$，接下来 $n$ 行 $l_i,r_i$，接下来 $n-1$ 行 $u,v$。

输入：

1
3
1 2
2 3
1 3
1 2
2 3

输出：

4

取 $a=(1,3,1)$：$|1-3|+|3-1|=4$。

数据范围：$1\le t\le 5$，$2\le n\le 10^5$，$1\le l_i\le r_i\le 10^9$（答案用 long long）。