C++ 解法, 执行用时: 544ms, 内存消耗: 33176K, 提交时间: 2021-06-04 16:16:11

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
const int mod = 998244353;
int n,a[maxn],ans;
vector<int>vec[maxn];
int siz[maxn],vis[maxn],mx[maxn],root,sumn;
typedef pair<int,int>p;
p res[maxn]; int top;
void getroot(int u,int fa)
{
	siz[u] = 1, mx[u] = 0;
	for( auto v:vec[u] )
	{
		if( vis[v] || v==fa )	continue;
		getroot(v,u);
		siz[u] += siz[v];
		mx[u] = max( mx[u],siz[v] );
	}
	mx[u] = max( mx[u],sumn-siz[u] );
	if( mx[u]<mx[root] )	root = u;
}
void dfs(int u,int fa,int dep)
{
	res[++top] = p( a[u],dep );
	for(auto v:vec[u] )
	{
		if( v==fa || vis[v] )	continue;
//		res[++top] = p( a[v],dep+1 );
		dfs( v,u,dep+1 );
	}
}
int calc(int u,int initdep)
{
	long long ans = 0, suf = 0;
	top = 0; dfs( u,u,initdep );
	sort( res+1,res+1+top );
	for(int i=top;i>=1;i--)
	{
//		ans = ( ans+min( res[i].first,a[u] )*res[i].second )%mod;
		ans = ( ans+1ll*res[i].first*(suf+1ll*res[i].second*(top-i)%mod)%mod )%mod;
		suf = ( suf+res[i].second )%mod;
	}
	return ans;
}
void solve(int u)
{
	vis[u] = 1; ans = ( ans+calc(u,0) )%mod;
	for(auto v:vec[u] )
	{
		if( vis[v] )	continue;
		ans = ( ans-calc(v,1) )%mod;
		sumn = siz[v], mx[root=0] = n+1;
		getroot(v,0); solve( root );
	}
}
int main()
{
	scanf("%d",&n );
	for(int i=1;i<=n;i++)	scanf("%d",&a[i] );
	for(int i=1;i<n;i++)
	{
		int l,r; scanf("%d%d",&l,&r);
		vec[l].push_back( r ); vec[r].push_back( l );
	}
	sumn = n, mx[root=0] = n+1;
	getroot(1,0); solve(1);
	printf("%d",(1ll*ans*2%mod+mod)%mod );
}