思路：我们定义两个数组，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][2],bob[Maxn][2],a[Maxn],b[Maxn],n,vi[Maxn]; void init() { memset(ant,0,sizeof(ant)); memset(bob,0,sizeof(bob)); memset(vi,0,sizeof(vi)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=0;i<=n;i++) head[i].clear(); } void dfs(int u) { int i,j,v,sz,temp,m1,m2; vi[u]=1; bool leaf=true; m1=m2=inf; sz=head[u].size(); for(i=0;i<sz;i++) { v=head[u][i]; if(vi[v]) continue; leaf=false; dfs(v); temp=min(bob[v][1],ant[v][0]); ant[u][0]+=temp; m1=min(m1,ant[v][1]-temp); temp=min(ant[v][1],bob[v][0]); bob[u][0]+=temp; m2=min(m2,bob[v][1]-temp); } if(leaf) { ant[u][1]=a[u]; ant[u][0]=a[u]/2; bob[u][1]=b[u]; bob[u][0]=b[u]/2; } else { ant[u][1]=ant[u][0]+min(a[u],m1+a[u]/2); ant[u][0]+=a[u]/2; bob[u][1]=bob[u][0]+min(b[u],m2+b[u]/2); bob[u][0]+=b[u]/2; } } int main() { int i,j,u,v,x; while(scanf("%d",&n)!=EOF) { init(); for(i=1;i<=n;i++) scanf("%d",a+i); for(i=1;i<=n;i++) scanf("%d",b+i); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); head[u].push_back(v); head[v].push_back(u); } dfs(1); printf("%d ",min(ant[1][1],bob[1][1])); } return 0; }