小Q又又又给你了一棵包含$n$个节点且根节点为 $1$ 的树，不同的是，每个节点有一个权值 ，现在，他又定义了一个规则，一条边的边权是这样计算的：

设 $a,b$ 为这条边两个端点的权值，那么这条边的边权是： $|a-k|+|b-k|$

其中 $k$ 是一个常数，小Q就是想让你求出一个 $k$，使得所有边权和最小。

第一行一个整数 $n$，表示点的个数。

第二行 $n$ 个整数，依次表示这 $n$ 个点的点权。

接下来 $n-1$ 行，每行两个数 $l,r$，表示 $l$ 是 $r$ 的父亲节点。

一行一个整数，表示最小的边权和。

样例输入 1

3
1 2 3
1 2
1 3

样例输出 1

3

样例输入 2

5
7 6 4 2 3
1 2
2 3
2 4
4 5

样例输出 2 14 code:

#include<bits/stdc++.h>
using namespace std;
int n;
struct jjj{
	int a,f,z;
}ak[1000005];
bool cmp(jjj qq,jjj ss){
	return qq.a<ss.a;
}
int main(){
	scanf("%d",&n);
	for(int i(1);i<=n;i++)
	scanf("%d",&ak[i].a);
	for(int i(1);i<n;i++)
	scanf("%d%d",&ak[i].f,&ak[i].z);
	sort(ak+1,ak+n+1,cmp);
	int k1=ak[(1+n)/2].a,k2=ak[k1+1].a;
	long long ans1=0,ans2=0;
	for(int i(1);i<n;i++)
	ans1+=abs(ak[ak[i].f].a-k1)+abs(ak[ak[i].z].a-k1);
	for(int i(1);i<n;i++)
	ans2+=abs(ak[ak[i].f].a-k2)+abs(ak[ak[i].z].a-k2);
	cout<<min(ans1,ans2);
	return 0;
}

求助QWQ,样例2过不了