hduoj 6725 Diversity - 百度之星 2019

目录

1. 输入
2. 输出
3. 输入样例
4. 输出样例

题目描述 http://acm.hdu.edu.cn/showproblem.php?pid=6725

给你一棵n个点的树，对于节点i，你要给它标上一个[li,ri]之间的数，要求所有边两端节点上标的数字的差的绝对值的总和最大。

输入

第一行一个整数T(1≤T≤5)表示数据组数。对于每组数据格式如下。

第一行一个正整数 n(2≤n≤105)。
接下来n−1行，每行两个正整数 u,v(1≤u,v≤n)，表示一条边。
接下来n行，第i行两个正整数li,ri(1≤li≤ri≤109)。

输出

对于每组数据，一个整数表示答案。

输入样例

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

输出样例

16

#include <cstdio> 
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int maxn=1e5+50;
vector<int> edge[maxn];

ll dp[maxn][2];
ll l[maxn];
ll r[maxn];

void dfs(int cur) {
	for(int i = 0;i < edge[cur].size(); i++) {
		int next = edge[cur][i];
		dfs(next);
		dp[cur][0] += max(dp[next][0] + abs(l[cur]-l[next]), dp[next][1] + abs(l[cur]-r[next]));
		dp[cur][1] += max(dp[next][0] + abs(r[cur]-l[next]), dp[next][1] + abs(r[cur]-r[next]));
	}
}


int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			edge[i].clear();
			dp[i][0] = 0;
			dp[i][1] = 0;
		}
		for (int i = 1; i < n; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			edge[a].push_back(b);
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", l + i, r + i);
		}
		dp[0][0] = 0;
		dp[0][1] = 0;
		dfs(1);
		ll maxv = 0;
		printf("%I64d\n", max(dp[1][0], dp[1][1]));
	}
	return 0;
}

参考 https://blog.csdn.net/qq_43083173/article/details/100178618