首先如果点权全都为正，就可以直接选所有的点。
活在梦里。。
考虑枚举一个点\(i\)，作为我们选择的集合中的一个点。
然后我们把另一个点\(j\)选入集合的时候必须把两棵树中\(i\)和\(j\)路径上的点全都选入集合。
似乎想到了什么。
闭合子图。
不就是一个最大权闭合子图吗。
然后我们按最大权闭合子图的模型建图。
所有正权的点跟\(S\)连容量为权值的边。
所有负权的点跟\(T\)连容量为权值绝对值的边。
我们把枚举的i作为两个树上的根。
然后每一个点跟两颗树上的\(father\)连容量为\(INF\)的边。
然后正权总和-最小割就是答案。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=1e9;
const int N=110;
int cnt,head[N];
struct edge{
int to,nxt,flow;
}e[N*6];
void add_edge(int u,int v,int flow){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
e[cnt].flow=flow;
}
int cn,hed[N];
struct ed{
int to,nxt;
}ee[N*2];
void add(int u,int v){
cn++;
ee[cn].nxt=hed[u];
ee[cn].to=v;
hed[u]=cn;
}
int f1[N];
void dfs1(int u,int f){
f1[u]=f;
for(int i=hed[u];i;i=ee[i].nxt){
int v=ee[i].to;
if(v==f)continue;
dfs1(v,u);
}
}
int f2[N];
void dfs2(int u,int f){
f2[u]=f;
for(int i=hed[u];i;i=ee[i].nxt){
int v=ee[i].to;
if(v==f)continue;
dfs2(v,u);
}
}
int dis[N],S,T;
bool bfs(){
memset(dis,-1,sizeof(dis));
dis[S]=0;
queue<int> q;
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]==-1&&e[i].flow){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if(dis[T]==-1)return false;
return true;
}
int dfs(int u,int f){
if(u==T||f==0)return f;
int used=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]==dis[u]+1&&e[i].flow){
int w=dfs(v,min(f-used,e[i].flow));
if(w){
e[i].flow-=w;
e[i^1].flow+=w;
used+=w;
if(used==f)return f;
}
}
}
if(used==0)dis[u]=-1;
return used;
}
int tmp;
void Dinic(){
while(bfs())tmp+=dfs(S,INF);
}
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;;
}
int n,a[N],tot,ans;
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++){
int u=read()+1,v=read()+1;
add(u,v);add(v,u);
}
for(int i=1;i<n;i++){
int u=read()+n+1,v=read()+n+1;
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++){
dfs1(i,0);dfs2(i+n,0);
cnt=1;memset(head,0,sizeof(head));tot=0;
S=0,T=n+1;
for(int j=1;j<=n;j++)
if(a[j]<0)add_edge(j,T,-a[j]),add_edge(T,j,0);
else add_edge(S,j,a[j]),add_edge(j,S,0),tot+=a[j];
for(int j=1;j<=n;j++){
if(j==i)continue;
add_edge(j,f1[j],INF);add_edge(f1[j],j,0);
add_edge(j,f2[j+n]-n,INF);add_edge(f2[j+n]-n,j,0);
}
tmp=0;
Dinic();
ans=max(ans,tot-tmp);
}
printf("%d",ans);
return 0;
}