百度之星 Diversity （简单树形dp）

题意描述Diversity给你一棵n个点的树对于节点ii你要给它标上一个[l​i​​,r​i​​]之间的数要求所有边两端节点上标的数字的差的绝对值的总和最大。Input第一行一个整数T T(1≤T≤5)表示数据组数。对于每组数据格式如下。第一行一个正整数n(2≤n≤10​5​​)。接下来n-1行每行两个正整数 u, v(1≤u,v≤n)表示一条边。接下来nn行第ii行两个正整数l​i​​,r​i​​(1 ≤ l​i ​​≤ r​i ​​≤ 10^​9​​)。Output对于每组数据一个整数表示答案。Sample Input1 5 1 2 2 3 3 4 4 5 1 5 2 7 7 9 5 8 3 4Sample Output16思路树形dp入门题开始考虑只要对于每一个节点要么选择最左端要么选择最右端点显然这一策略是正确的。然后假设根节点权值确定整棵树的状态即确定然后按照dfs序正向状态转移两种状态取较大者作为最优解。这种贪心策略是不对的如父节点到子节点的左右边界差值一致这时候该怎么选择。但如果逆向考虑就不会有类似问题了这一点倒是考虑到了这写出了代码但状态转移条件搞错了具体说错误原因转移时只考虑了父节点和子节点间差值的大小而没有加上子节点所在子树的整个权值所以导致选择出的并不是全局最优解。代码实现#include stdio.h #include string.h #include iostream #include algorithm #define inf 0x3f3f3f3f using namespace std; const int N 1e5100; const int M 2e5100; int head[N],ver[M],Next[M],tot; void add(int x,int y) { ver[tot]y; Next[tot]head[x]; head[x]tot; } long long dp[N][2]; int Left[N],Right[N]; void dfs(int x,int pre) { long long a,b,c,d; for(int ihead[x]; i; iNext[i]) { int yver[i]; if(i(pre^1))continue; dfs(y,i); aabs(Left[y]-Left[x]); babs(Right[y]-Left[x]); cabs(Left[y]-Right[x]); dabs(Right[y]-Right[x]); //转移条件易错 if(dp[y][0]adp[y][1]b) dp[x][0]dp[y][0]a; else dp[x][0]dp[y][1]b; if(dp[y][0]cdp[y][1]d) dp[x][1]dp[y][0]c; else dp[x][1]dp[y][1]d; } } int main() { #ifdef MYHOME_Wjvje freopen(input.txt,r,stdin); #endif int t,n; scanf(%d,t); long long ans; while(t--) { tot1; ans0; scanf(%d,n); memset(head,0,sizeof(head)); memset(Next,0,sizeof(Next)); memset(dp,0,sizeof(dp)); for(int i1; in; i) { int x,y; scanf(%d%d,x,y); add(x,y); add(y,x); } for(int i1; in; i) scanf(%d%d,Left[i],Right[i]); dfs(1,0); ansmax(dp[1][0],dp[1][1]); printf(%lld\n,ans); } return 0; }THE END;