思路：我们定义两个数组，ant[Maxn][2],bob[Maxn][2]。ant[i][0]表示还未确定哪个城市被全费用占领，ant[i][1]表示确定了哪个城市被全费用占领。那么ant[i][0]的转移方程是ant[u][0]+=min(ant[v][0],bob[v][1]);即与它相连的那个城市也未确定全费用占领的城市，或者被bob占领，且确定了全费用。
由于ant[u][0]表示未确定，故不能从ant[v][1]的确定状态转移过来。
ant[u][1]=ant[u][0]+min(a[u],m1+a[u]/2);对于u节点确定了全费用占领城市，那么要么就是自己全费用占领，或者是他的某个相邻节点确定了全费用，所以其m1=min(m1,ant[v][1]-min(ant[v][0],bob[v][1]));表示选择相邻的某个节点确定全费用，那么就要把其未确定全费用的从ant[u][0]里减去，在赋值给ant[u][1]。
同理bob一样。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#define Maxn 110
#define inf 0x7fffffff
using namespace std;
vector<int> head[Maxn];
int ant[Maxn][],bob[Maxn][],a[Maxn],b[Maxn],n,vi[Maxn];
void init()
{
memset(ant,,sizeof(ant));
memset(bob,,sizeof(bob));
memset(vi,,sizeof(vi));
memset(a,,sizeof(a));
memset(b,,sizeof(b));
for(int i=;i<=n;i++)
head[i].clear();
}
void dfs(int u)
{
int i,j,v,sz,temp,m1,m2;
vi[u]=;
bool leaf=true;
m1=m2=inf;
sz=head[u].size();
for(i=;i<sz;i++)
{
v=head[u][i];
if(vi[v]) continue;
leaf=false;
dfs(v);
temp=min(bob[v][],ant[v][]);
ant[u][]+=temp;
m1=min(m1,ant[v][]-temp);
temp=min(ant[v][],bob[v][]);
bob[u][]+=temp;
m2=min(m2,bob[v][]-temp);
}
if(leaf)
{
ant[u][]=a[u];
ant[u][]=a[u]/;
bob[u][]=b[u];
bob[u][]=b[u]/;
}
else
{
ant[u][]=ant[u][]+min(a[u],m1+a[u]/);
ant[u][]+=a[u]/;
bob[u][]=bob[u][]+min(b[u],m2+b[u]/);
bob[u][]+=b[u]/;
}
}
int main()
{
int i,j,u,v,x;
while(scanf("%d",&n)!=EOF)
{
init();
for(i=;i<=n;i++)
scanf("%d",a+i);
for(i=;i<=n;i++)
scanf("%d",b+i);
for(i=;i<n;i++)
{
scanf("%d%d",&u,&v);
head[u].push_back(v);
head[v].push_back(u);
}
dfs();
printf("%d\n",min(ant[][],bob[][]));
}
return ;
}