C++11(clang++ 3.9) 解法, 执行用时: 81ms, 内存消耗: 8540K, 提交时间: 2019-11-04 18:35:31

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int n,d[100005],c[100005];
int cnt,head[100005],flag;
int f[100005],g[100005],F[100005];//f 父亲 g自己 F 01背包
struct q {
	int next,to;
} e[200005];
void add(int x,int y) {
	e[++cnt].next=head[x],e[cnt].to=y,head[x]=cnt;
	e[++cnt].next=head[y],e[cnt].to=x,head[y]=cnt;
}
void dfs(int v,int fa) {
	int i,u,sc=0,j;
	for(i=head[v]; i; i=e[i].next) {
		u=e[i].to;
		if(u==fa)continue;
		sc+=c[u];
		dfs(u,v);
	}
	if(flag) {
		for(i=1; i<=sc; i++)F[i]=inf;
		F[0]=0;
		for(i=head[v]; i; i=e[i].next) {
			u=e[i].to;
			if(u==fa)continue;
			for(j=sc; j>=0; --j) {
				int a=F[j]+f[u];
				int b=j<c[u]?inf:F[j-c[u]]+g[u];
				F[j]=min(a,b);
			}
		}
		int mmin=inf;
		for(j=0; j<=sc; ++j) {
			if(j+c[fa]<=d[v]) {
				mmin=min(mmin,F[j]-j);
			} else break;
		}
		f[v]=mmin+d[v]-c[fa];
		mmin=inf;
		for(j=0; j<=sc; ++j) {
			if(j<=d[v]) {
				mmin=min(mmin,F[j]-j);
			} else break;
		}
		g[v]=mmin+d[v];
	}else{
		int t1=0,t2=0;
		for(i=head[v]; i; i=e[i].next) {
			u=e[i].to;
			if(u==fa)continue;
			if(!c[u])t1+=f[u];
			else{
				if(f[u]==g[u])t1+=g[u],t2+=c[u];
				else t1+=f[u];
			}
		}
		g[v]=t1+max(0,d[v]-t2);
		f[v]=t1+max(0,d[v]-t2-c[fa]);
	}
	return;
}
int main() {
	int i,x,y;
	scanf("%d",&n);
	for(i=1; i<=n; ++i)scanf("%d",&d[i]);
	for(i=1; i<=n; ++i){
		scanf("%d",&c[i]);
		if(c[i]>1)flag=1;
	}
	for(i=1; i<n; ++i) {
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	dfs(1,0);
	printf("%d",g[1]);
}