DiversityTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 27 Accepted Submission(s): 19Problem 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 Input1 5 1 2 2 3 3 4 4 5 1 5 2 7 7 9 5 8 3 4Sample Output16Source2019 年百度之星·程序设计大赛 - 复赛Recommendheyang | 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],状态转移即可。#includebits/stdc.h using namespace std; typedef long long ll; const int maxn 100010; int n, l[maxn], r[maxn]; ll dp[maxn][2]; vectorint 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 i1; in; 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 i1; in; i) scanf(%d%d, l[i], r[i]); dfs(1, -1); printf(%lld\n, max(dp[1][0], dp[1][1])); } return 0; }