题意

给定一颗树，点有点权，将树分为若干条链，最大化所有链的极差和。

思路

一个很自然的想法是短的链一定比长的链优，发现是假的，比如：

1->2->99->100

在这个例子上就是长的链更优。

虽然思路假了，但是在这个思路上拓展，考虑什么时候短的链比长的链更优，如：

1->99->2->100

观察发现，当一个链非单调，或者说将其拍到坐标系上的图像是曲折的，那么将每个折线单独取出来变成单独的链绝对是不会更劣的。

如图，将蓝色的链变成绿色的链，答案更优。

于是我们得到了，最后链一定是单调的。

一个显然的 dp 思路是定义 $f_{u,k,0/1}$ 为节点 $u$ 的子树中，当前的链上最大或最小值为 $k$，当前（从下往上）为递减 / 递增的最大经验值。

考虑优化，利用单调的这个性质，可以将每条链的贡献分摊到每个点上，将费用提前计算，将极差转化为两两之间的差，状态变为 $f_{u,0/1}$ 为 $u$ 的子树内，当前是递减 / 递增的最大答案，转移就简单了，具体可以看代码。

#include<bits/stdc++.h>
#define int long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
int n,w[N],f[N][2];
vector<int>g[N];
inline void add(int u,int v)
{
	g[u].push_back(v);
	return;
}
void dfs(int u)
{
	int sum=0;
	f[u][0]=f[u][1]=0;
	for(int v:g[u]){
		dfs(v);
		sum+=max(f[v][0],f[v][1]);
	}
	f[u][0]=f[u][1]=sum;
	//0:从下到上递减
	int maxn=sum;
	for(int v:g[u]){
		if(w[v]>=w[u]){
			maxn=max(maxn,sum-max(f[v][0],f[v][1])+f[v][0]+w[v]-w[u]);
		}
	}
	f[u][0]=maxn;
	maxn=sum;
	for(int v:g[u]){
		if(w[v]<=w[u]){
			maxn=max(maxn,sum-max(f[v][0],f[v][1])+f[v][1]+w[u]-w[v]);
		}
	}
	f[u][1]=maxn;
//	cout << u << " " << f[u][0] << " " << f[u][1] << '\n';
	return;
}
signed main()
{
	n=read();
	F(i,1,n){
		w[i]=read();
	}
	F(i,2,n){
		int ui=read(),vi=read();
		add(ui,vi);
	}
	dfs(1);
	cout << max(f[1][0],f[1][1]) << '\n';
	return 0;
}
/*

*/