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; }
