題意：一棵樹，每個節點可以染兩種顏色，每種顏色都有一定的代價，有一個特殊的地方就是如果相鄰點已經被染了相同的顏色，當前點染這種顏色的時候只需要一半的代價
最後問：將整棵樹都染色最少需要多大代價。
DP的時候要先想好怎麼去利用限制條件將狀態描述好，因為跟一個點相鄰的點中如果有一個點被染成相同顏色且用了全部代價，那麼這個點染這種顏色只需要一半的代價了，所以，我們可以設計這樣的狀態，
F[u][0] : 對u染第一種顏色的時候還沒有選定染全色的節點
F[u][1]: 對u染第一種顏色，已經選定了染全色的節點
g[u][0],g[u][1]就是第二種顏色，狀態類似
在轉移的時候，我們可以將子節點所有的已求好的狀態都列出來
比如 要求f[u][0]
子節點的狀態 f[v][0],f[v][1],g[v][0],g[v][1] 均已經求好
則可得 ： f[u][0]+=min(g[v][1],f[v][0]) ,因為f[u][0]表示u染第一種顏色的時候還沒有確定跟u相連的點中那個點染全色，所以不能從f[v][1]這個已經確定的狀態轉移過來
在求f[u][1]的時候，要麼我們對u節點染全色，要麼在u的某個子樹中染全色，所以f[u][1]=f[u][0]+min(a[u],ma);
其中 ma表示f[v][1]-min(g[v][1],f[v][0])的最小值，因為要挑選一棵子樹的f[v][1]狀態來替換原來加進來的狀態
最後f[u][0]在加上a[u]/2即可；
最後注意，如果是葉子節點要特判一下，葉子節點沒有子樹節點。
[cpp]
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int inf = 100000;
const int maxn = 101;
vector<int> edge[maxn];
int a[maxn],b[maxn];
int f[maxn][2],g[maxn][2];
void dfs(int u,int fa)
{
f[u][0]=0;
g[u][0]=0;
int sz=edge[u].size();
int m1=inf,m2=inf;
bool leaf=true;
for(int i=0;i<sz;i++)
{
int v=edge[u][i];
if(v==fa) continue;
dfs(v,u);
leaf=false;
int tmp=min(f[v][0],g[v][1]);
f[u][0]+=tmp;
m1=min(m1,f[v][1]-tmp);
tmp=min(g[v][0],f[v][1]);
g[u][0]+=tmp;
m2=min(m2,g[v][1]-tmp);
}
if(leaf)
{
f[u][1]=a[u];
f[u][0]=a[u]/2;
g[u][1]=b[u];
g[u][0]=b[u]/2;
}
else
{
//printf("m1=%d\n",m1);
//printf("f[u][0]=%d\n",f[u][0]);
f[u][1]=f[u][0] + min(a[u],m1+a[u]/2);
f[u][0]+=a[u]/2;
//printf("%d %d\n\n",f[u][0],f[u][1]);
g[u][1]=g[u][0] + min(b[u],m2+b[u]/2);
g[u][0]+=b[u]/2;
//printf("u=%d bu=%d %d %d\n",u,b[u],g[u][0],g[u][1]);
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<=n;i++) edge[i].clear();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
printf("%d\n",min(f[1][1],g[1][1]));
}
return 0;
}
