本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-07 15:01:49

\/*

可以发现，这个划分的过程把树分成了n条链。
如果每个点单独，那么有最小值0，要想取得最大值，要将将递增或递减的分在不同的链里。
设dp[u][0\/1]为以u为节点，当前点属于上升链还是递减链。
u由三种可能的情况：
1.u点不属于任何孩子链，每个孩子在单独的链。
2.在某个孩子连接的递减的链上
3.在某个孩子连接的递增链上
*\/ 
#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n;
ll w[N],dp[N][2];
vector<int> t[N];
void dfs(int u) {
	ll sm=0;
	for(auto v:t[u]) {
		dfs(v);
		sm+=max(dp[v][0],dp[v][1]);
	}
	dp[u][0]=dp[u][1]=sm;
	\/\/把当前节点放在哪个链上呢？都试试取最优质，扣去这个v链，u在v链上产生新的价值。
	for(auto v:t[u]) {
		if(w[v]<=w[u])\/\/在递减的链上
			dp[u][0]=max(dp[u][0],sm-max(dp[v][0],dp[v][1])+w[u]-w[v]+dp[v][0]);
		if(w[v]>=w[u])\/\/在递增的链上 ，u在
			dp[u][1]=max(dp[u][1],sm-max(dp[v][0],dp[v][1])+w[v]-w[u]+dp[v][1]);
	}
	return ;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%lld",&w[i]);
	for(int i=1; i<n; i++) {
		int x,y;
		scanf("%d%d",&x,&y);\/\/有向树
		t[x].push_back(y);
	}
	dfs(1);
	printf("%lld\n",max(dp[1][0],dp[1][1]));
	return 0;
}