CF1528A-Parsa's Humongous Tree
题目大意：给出一棵树，树的编号为i的结点上可以写一个在区间[li,ri]上的值。一条边的权为它所连接的两个顶点上写的值，问这棵树的所有边的权值之和最大可以是多少。
设结点x的权值为ax，它的子结点为son1,son2,son3,...,sons，那么结点x对整棵树的权值之和所能做出的贡献是
i=1∑s∣ax−asoni∣
假设各个asoni的值都确定了。对于结点x，如果它的子结点中值大于ax的节点个数超过值小于ax的节点个数，ax的值取到lx最优；如果它的子结点中值小于ax的节点个数超过值大于ax的节点个数，ax的值取到rx最优。因此每个点x的可能取值只有lx和rx两种。跑个树形DP就出来了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
int head[100005], tot;
long long l[100005], r[100005], dp[2][100005];
struct ege
{
int to, nex;
} edge[200005];
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].nex = head[u];
head[u] = tot++;
}
void dfs(int root, int pre)
{
dp[0][root] = dp[1][root] = 0;
int s, i;
for (i = head[root]; i; i = edge[i].nex)
{
s = edge[i].to;
if (s != pre)
{
dfs(s, root);
dp[0][root] += max(dp[0][s] + llabs(l[s] - l[root]), dp[1][s] + llabs(r[s] - l[root]));
dp[1][root] += max(dp[0][s] + llabs(l[s] - r[root]), dp[1][s] + llabs(r[s] - r[root]));
}
}
}
int main()
{
int _, n, i, u, v;
scanf("%d", &_);
while (_--)
{
scanf("%d", &n);
for (i = 0; i <= n; i++)
head[i] = 0;
tot = 1;
for (i = 1; i <= n; i++)
scanf("%lld%lld", &l[i], &r[i]);
for (i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, -1);
printf("%lld\n", max(dp[0][1], dp[1][1]));
}
return 0;
}
|