百度之星 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 Input

1 5 1 2 2 3 3 4 4 5 1 5 2 7 7 9 5 8 3 4

Sample Output

16

思路：

树形dp入门题？？？

开始考虑只要对于每一个节点，要么选择最左端，要么选择最右端点，显然，

这一策略是正确的。

然后假设根节点权值确定，整棵树的状态即确定，然后按照dfs序正向状态转移，

两种状态取较大者作为最优解。（这种贪心策略是不对的，如父节点到子节点的左右

边界差值一致，这时候该怎么选择？）。

但如果逆向考虑就不会有类似问题了，这一点倒是考虑到了，这写出了代码，

但状态转移条件搞错了，具体说错误原因转移时只考虑了父节点和子节点间差值的

大小，而没有加上子节点所在子树的整个权值，所以导致选择出的并不是全局最优解。

代码实现：

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #define inf 0x3f3f3f3f using namespace std; const int N = 1e5+100; const int M = 2e5+100; 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 i=head[x]; i; i=Next[i]) { int y=ver[i]; if(i==(pre^1))continue; dfs(y,i); a=abs(Left[y]-Left[x]); b=abs(Right[y]-Left[x]); c=abs(Left[y]-Right[x]); d=abs(Right[y]-Right[x]); //转移条件易错 if(dp[y][0]+a>dp[y][1]+b) dp[x][0]+=dp[y][0]+a; else dp[x][0]+=dp[y][1]+b; if(dp[y][0]+c>dp[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--) { tot=1; ans=0; scanf("%d",&n); memset(head,0,sizeof(head)); memset(Next,0,sizeof(Next)); memset(dp,0,sizeof(dp)); for(int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1; i<=n; i++) scanf("%d%d",&Left[i],&Right[i]); dfs(1,0); ans=max(dp[1][0],dp[1][1]); printf("%lld\n",ans); } return 0; }

THE END;