Diversity
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 27 Accepted Submission(s): 19
Problem Description
给你一棵n个点的树，对于节点i，你要给它标上一个[li,ri]之间的数，要求所有边两端节点上标的数字的差的绝对值的总和最大。
Input
第一行一个整数T(1≤T≤5)表示数据组数。对于每组数据格式如下。
第一行一个正整数 n(2≤n≤105)。
接下来n?1行，每行两个正整数 u,v(1≤u,v≤n)，表示一条边。
接下来n行，第i行两个正整数li,ri(1≤li≤ri≤109)。
Output
对于每组数据，一个整数表示答案。
Sample Input
1 5 1 2 2 3 3 4 4 5 1 5 2 7 7 9 5 8 3 4
Sample Output
16
Source
2019 年百度之星·程序设计大赛 - 复赛
Recommend
heyang | We have carefully selected several similar problems for you: 6730 6729 6728 6727 6726
分析：
简单树形DP，从叶子节点到根更新，dp[i][0]表示i节点选择l[i],dp[i][1]表示i节点选择r[i],状态转移即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n, l[maxn], r[maxn];
ll dp[maxn][2];
vector<int> G[maxn];void dfs(int u, int fa)
{dp[u][0] = dp[u][1] = 0;for(int v : G[u])if(v != fa){dfs(v, u);dp[u][0] += max(dp[v][0]+abs(l[v]-l[u]), dp[v][1]+abs(r[v]-l[u]));dp[u][1] += max(dp[v][0]+abs(l[v]-r[u]), dp[v][1]+abs(r[v]-r[u]));}
}
int main()
{int T;scanf("%d", &T);while(T--){scanf("%d", &n);for(int i=1; i<=n; i++)G[i].clear();for(int i = 1; i < n; ++i){int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}for(int i=1; i<=n; i++)scanf("%d%d", &l[i], &r[i]);dfs(1, -1);printf("%lld\n", max(dp[1][0], dp[1][1]));}return 0;
}