考虑到这一条链肯定是单调递增或者单调递减更优。
因为若不是单调的可以考虑把这个链拆成多个单调的链。
因为若最大最小值不在链的两端，明显把两端不需要的可以拆出去；否则例如链的顶比底大，则肯定存在 \(x > x' < y' > y\)，\(x, y\) 为链的两端，那么 \(x - x' + y - y'\) 的收益明显比 \(x - y\) 大。
那就可以考虑 \(\text{DP}\)。
令 \(f_{u, 0 / 1}\) 为考虑 \(u\) 的子树 \(u\) 所在的链从底至顶是单调递增 / 递减的最大收益。
例如链从底至顶递增，考虑用 \(a_{fa} - a_u\) 来拆贡献，最后两两抵消就只剩下顶 \(-\) 底了。
类似的，若是递减考虑用 \(a_u - a_{fa}\) 来拆贡献。
于是令 \(S = \sum\limits_{v\in son_u} \max\{f_{v, 0}, f_{v, 1}\}\)。
对于 \(a_u > a_v\)，链从底至顶递增，有 \(f_{u, 0} = S + \max\{0, f_{v, 0} + a_u - a_v - \max\{f_{v, 0}, f_{v, 1}\}\}\)。
代表 \(u\) 有两种选择，直接作为新链的底端或者接在一条从底至顶递增的链。
对于 \(a_u < a_v\)，\(f_{u, 1}\) 的转移同理。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using i64 = long long;
const int maxn = 1e5 + 10;
int n;
int w[maxn];
std::vector<int> son[maxn];
i64 f[maxn][2];
void dfs(int u) {
i64 sum = 0;
for (int v : son[u]) {
dfs(v);
sum += std::max(f[v][0], f[v][1]);
}
f[u][0] = sum, f[u][1] = sum;
for (int v : son[u]) {
if (w[u] > w[v]) f[u][0] = std::max(f[u][0], sum - std::max(f[v][0], f[v][1]) + f[v][0] + w[u] - w[v]);
else f[u][1] = std::max(f[u][1], sum - std::max(f[v][0], f[v][1]) + f[v][1] - w[u] + w[v]);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i < n; i++) {
int x, y; scanf("%d%d", &x, &y);
son[x].push_back(y);
}
dfs(1);
printf("%lld\n", std::max(f[1][0], f[1][1]));
return 0;
}