1.题目翻译

传送门
帕萨在n个顶点上有一棵巨大的树。

在每个顶点v上，他写了两个整数lv和rv。

为了使帕萨的树看起来更加雄伟，尼玛想给它指定一个数字av（lv）≤影音≤rv）到每个顶点v，以使帕萨树的美最大化。

尼玛的美感相当奇怪。他把这棵树的美丽定义为|au?av| 的总和覆盖树的所有边缘（u，v）。

因为帕萨的树太大了，尼玛不能靠自己最大限度地美化它。你的任务是为帕萨的树找到最大可能的美。

输入

第一行包含一个整数t（1≤T≤250）-测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（2≤N≤105）-Parsa树中的顶点数。

以下n行中的第i行包含两个整数li和ri（1≤锂≤ri≤109).

下一个n?1行包含两个整数u和v（1≤u、五≤n、 u≠v）这意味着在帕萨树的顶点u和v之间有一条边。

保证给定的图是一棵树。

保证所有测试用例中n的总和不超过2?105

输出

对于每个测试用例，打印Parsa树的最大可能美。
inputCopy
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
outputCopy
7
8
62

2.解题思路

和没有上司的舞会类似。
因为美丽值的定义是一条边上两点的权值差的绝对值，要想获得最大的美丽值，每条边上的点一定都取到极值（一个取最大，一个取最小），然后统计所有边的美丽值的和。
朴素的想法是枚举一条边上某个点取最大值，然后与其相连的点取最小值，或取最小值，然后与其相连的点取最大值，这样去枚举一下所有情况。
这就有点像树形dp了，枚举某个点的取值情况，然后去推出他父亲的取值情况，如此反复。
dp[u][ 0/1] 表示当前节点u取0（最小值）/ 1（最大值）时的最大美丽值之和。
v 表示与
可以设计出如下转移方程：

//字节点v取min的最大值 + abs(u取min - v取min), 点v取max的 + abs(u取mi - v取ma) 
dp[u][0] += max(dp[v][0] + abs(l[u] - l[v]), dp[v][1] + abs(l[u] - r[v])); 
// 和上面类似
dp[u][1] += max(dp[v][0] + abs(r[u] - l[v]), dp[v][1] + abs(r[u] - r[v]));

最后先建图，再跑一遍树形dp,最后输出根节点的最大值情况。

3.参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, t, u, v;
ll l[N], r[N], f[N];
vector<int> m[N];
ll dp[N][2];
void dfs(int u, int f) // 当前节点u， 其父节点f
{
    for (int i = 0; i < m[u].size(); ++i) { // 遍历与当前节点相连的所有边
        int v = m[u][i]; //相连的点
        if (v == f) continue; 
        dfs(v, u);
        //状态转移
        dp[u][0] += max(dp[v][0] + abs(l[u] - l[v]), dp[v][1] + abs(l[u] - r[v])); 
        dp[u][1] += max(dp[v][0] + abs(r[u] - l[v]), dp[v][1] + abs(r[u] - r[v]));
    }
}
void solve()
{
    cin >> n;
    memset(dp, 0, sizeof dp); // 初始化dp数组
    for (int i = 1; i <= n; ++i) {
        m[i].clear(); // 初始化图
        cin >> l[i] >> r[i]; // 输入每个点的取值范围mi ~ mx
        f[i] = 0; //初始化标记数组
    }
    //建树
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        //标记当前点连了几次
        f[u]++; f[v]++;
        //存双向边u -> v, v -> u
        m[u].push_back(v);
        m[v].push_back(u);
    }
    //设置根节点
    int cnt = 0;
    for (int i = 1; i <= n; ++i) //寻找到只连接一次的点作为根节点
    if (f[i] == 1) {
        cnt = i;
        break;
    }
    dfs(cnt, -1); // 开始搜索
    //最后输出根节点两种情况下的最值
    cout << max(dp[cnt][0], dp[cnt][1]) << endl;
    
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //关闭同步输入输出流，加速cin读入
    cin >> t;
    while (t--) solve();
    return 0;
}