#include <bits/stdc++.h>
using namespace std;
const int N = 6e3+5;
int n,a[N],f[N][2];
vector<int>e[N];
void dfs(int x,int fa){
	f[x][1] = a[x];
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		f[x][0]+=max(f[v][0],f[v][1]);
		f[x][1]+=f[v][0];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	cout<<max(f[1][0],f[1][1])<<endl;
	return 0;
}

/*
f[x][0]管x及x的子树和x的父亲的最小花费
f[x][1]管x及x的子树的最小花费
f[x][2]管x的子树的最小花费
f[x][0] = 1+sigma(f[v][2])
f[x][1] = min(f[v][0]+sigma(f[t][1])
f[x][2] = sigma(f[v][1])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,f[N][4];
vector<int>e[N];
void dfs(int x,int fa){
	f[x][0] = 1;
	int sum = 0;
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		sum+=f[v][1];
		f[x][0]+=f[v][2];
		f[x][2]+=f[v][1];
	}
	f[x][1] = 1e9;
	for(auto v:e[x]){
		if(v==fa)continue;
		f[x][1] = min(f[x][1],f[v][0]+sum-f[v][1]);
	}
	for(int i=1;i<=2;i++){
		f[x][i] = min(f[x][i],f[x][i-1]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	cout<<f[1][1]<<endl;
	return 0;
}

/*
f[x][0]管x及x的子树和x的父亲的最小花费
f[x][1]管x及x的子树的最小花费
f[x][2]管x的子树的最小花费
f[x][0] = 1+sigma(f[v][2])
f[x][1] = min(f[v][0]+sigma(f[t][1])
f[x][2] = sigma(f[v][1])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,f[N][4],a[N];
vector<int>e[N];
void dfs(int x,int fa){
	f[x][0] = a[x];
	int sum = 0;
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		sum+=f[v][1];
		f[x][0]+=f[v][2];
		f[x][2]+=f[v][1];
	}
	f[x][1] = 1e9;
	for(auto v:e[x]){
		if(v==fa)continue;
		f[x][1] = min(f[x][1],f[v][0]+sum-f[v][1]);
	}
	for(int i=1;i<=2;i++){
		f[x][i] = min(f[x][i],f[x][i-1]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,t,m;
		cin>>x>>t>>m;
		a[x] = t;
		for(int j=1;j<=m;j++){
			int y;
			cin>>y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
	}
	dfs(1,0);
	cout<<f[1][1]<<endl;
	return 0;
}

/*
f[x][0]管x、x的子树、父亲、爷爷的最小花费
f[x][1]管x、x的子树、父亲的最小花费
f[x][2]管x、x的子树的最小花费
f[x][3]管x的子树的最小花费
f[x][4]管x的子树的子树

f[x][0] = 1+sigma(f[v][4])
f[x][1] = f[v][0] + sigma(f[t][3])
f[x][2] = f[v][1] + sigma(f[t][2])
f[x][3] = sigma(f[v][2])
f[x][4] = sigma(f[v][3])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,f[N][5];
vector<int>e[N];
void dfs(int x,int fa){
	f[x][0] = 1;
	int sum2=0,sum3=0;
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		f[x][0]+=f[v][4];
		f[x][3]+=f[v][2];
		f[x][4]+=f[v][3];
		sum2+=f[v][2];
		sum3+=f[v][3];
	}
	f[x][1] = f[x][2] = 1e9;
	for(auto v:e[x]){
		if(v==fa)continue;
		f[x][1] = min(f[x][1],f[v][0]+sum3-f[v][3]);
		f[x][2] = min(f[x][2],f[v][1]+sum2-f[v][2]);
	}
	for(int i=1;i<=4;i++){
		f[x][i] = min(f[x][i],f[x][i-1]);
	}
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int x,y;
		cin>>x;
		e[i].push_back(x);
		e[x].push_back(i);
	}
	dfs(1,0);
	cout<<f[1][2]<<endl;
	return 0;
}

/*
f[x][i]x的子树通过最多i条边能到的点
f[x][i] = sigma(f[v][i-1])

g[x][i]x的子树外最多i条边能到x的点
g[x][i] = g[fa][i-1]+(f[fa][i-1]-f[x][i-1])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,f[N][25],a[N],g[N][25],k;
vector<int>e[N];
void dfs1(int x,int fa){
	f[x][0] = a[x];
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs1(v,x);
		for(int i=1;i<=k;i++){
			f[x][i] += f[v][i-1];	
		}
	}

}
void dfs2(int x,int fa){
	if(x!=1){
		for(int i=1;i<=k;i++){
			g[x][i] += g[fa][i-1];
			g[x][i]+=f[fa][i-1]-f[x][i-2];
		}	
	}
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs2(v,x);
	}

}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs1(1,0);
	for(int x=1;x<=n;x++){
		for(int i=1;i<=k;i++){
			f[x][i]+=f[x][i-1];
		}
	}
	
	dfs2(1,0);
	for(int i=1;i<=n;i++){
	//	cout<<f[i][k]<<" "<<g[i][k]<<endl;
		cout<<f[i][k]+g[i][k]<<endl;
	}
	return 0;
}