Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n;

#define MAXN 80

#define INF 0x3f3f3f3f

vector<int> v1[MAXN],v2[MAXN];

int val[MAXN];

int fa[MAXN];

bool v[MAXN];

void dfs1(int k)

{

	v[k] = true;

	for(vector<int>::iterator it = v1[k].begin();it != v1[k].end();++it)

	{

		if(v[*it])continue;

		fa[*it] = k;

		dfs1(*it);

	}

	return;

}

void dfs2(int k)

{

	v[k] = true;

	for(vector<int>::iterator it = v2[k].begin();it != v2[k].end();++it)

	{

		if(v[*it])continue;

		fa[*it] = k;

		dfs2(*it);

	}

	return;

}

struct edge

{

	int to,nxt,f;

}e[MAXN << 3];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int s,t;

int ch[MAXN];

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

bool bfs()

{

	memset(ch,-1,sizeof(ch));

	ch[s] = 0;

	queue<int> q;

	q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int dinic()

{

	int ans = 0,r;

	while(bfs())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);++a;++b;

		v1[a].push_back(b);v1[b].push_back(a);

	}

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);++a;++b;

		v2[a].push_back(b);v2[b].push_back(a);

	}

	int ans = 0;

	for(int rt = 1;rt <= n;++rt)

	{

		int sum = 0;

		memset(lin,-1,sizeof(lin));

		edgenum = 0;

		memset(v,false,sizeof(v));

		dfs1(rt);

		for(int i = 1;i <= n;++i)

		{

			if(i == rt)continue;

			add(i,fa[i],INF);

		}

		memset(v,false,sizeof(v));

		dfs2(rt);

		for(int i = 1;i <= n;++i)

		{

			if(i == rt)continue;

			add(i,fa[i],INF);

		}

		s = n + 1;t = s + 1;

		for(int i = 1;i <= n;++i)

		{

			if(val[i] > 0)sum += val[i];

			if(val[i] > 0)add(s,i,val[i]);

			else add(i,t,-val[i]);

		}

		ans = max(ans,sum - dinic());

	}

	cout << ans << endl;

	return 0;

}