树上区间取值 - 代码源竞赛平台

题目描述

蜗蜗得到一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$。第 $i$ 个节点有一个允许区间 $[l_i,r_i]$。

蜗蜗需要给每个节点选择一个整数 $x_i$，满足 $l_i\le x_i\le r_i$。对于连接节点 $u$ 和 $v$ 的一条边，这条边的价值为 $|x_u-x_v|$。整棵树的价值等于所有边的价值之和。

请你求出这棵树能够获得的最大价值。

输入格式

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

对于每组测试用例：

• 第一行包含一个整数 $n$，表示节点数量；
• 接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个节点的允许区间；
• 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 与节点 $v$ 之间有一条无向边。

输出格式

对于每组测试用例，输出一行一个整数，表示整棵树能够获得的最大价值。

样例

1
2
1 4
2 7
1 2

6

样例解释

给节点 $1$ 选择整数 $1$，给节点 $2$ 选择整数 $7$，唯一一条边的价值为 $|1-7|=6$。

数据范围

对于 100% 的数据，保证 $1\le T\le 250$，$2\le n\le 10^5$，$1\le l_i\le r_i\le 10^9$，$1\le u,v\le n$。

对于同一个输入文件中的所有测试用例，保证 $n$ 的总和不超过 $2\times 10^5$。每组测试用例中的边都构成一棵树。