#include <cstdio>#include <cstring>#include <algorithm>using std::fill;const int MAX_N = 1110;const int inf = 99999999;int head[MAX_N] , pnt[MAX_N*2] , nxt[MAX_N*2] ;int E;int n , K;int val[MAX_N];void add(int a,int b) { pnt[E] = b; nxt[E] = head[a]; head[a] = E++;}int dp[MAX_N][22];int son[MAX_N];void dfs(int u,int f) { son[u] = 1; dp[u][0] = val[u]; for(int i = head[u]; ~i; i = nxt[i]) { int v = pnt[i]; if(v == f) continue; dfs(v,u); son[u] += son[v]; for(int j = K; j >= 0; j--) { dp[u][j] += dp[v][0]; for(int k = 1; k <= j && k <= son[v]-1; k++) if(dp[u][j-k]!=inf){ dp[u][j] = std::min(dp[u][j] , dp[u][j-k] + dp[v][k]); } for(int k = 0; k <= j && k <= son[v]-1; k++) { dp[u][j] = std::min(dp[u][j],dp[u][j-k-1]) ; } } }}int gao() { int ans = dp[1][K]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= K; j++) if(j<=son[i]-1 && (K-j >= 1 && K-j <= n-1-(son[i]-1)) ){ ans = std::min(ans , dp[i][j]); } } return ans;}int main() { while(scanf("%d%d",&n,&K)!=EOF) { E = 0; memset(head,-1,sizeof(head)); for(int i = 1; i <= n; i++) scanf("%d",&val[i]); for(int i = 1,a,b; i < n; i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } fill(dp[0],dp[n+1],inf); dfs(1,-1); printf("%d ",gao()); for(int i = 1; i <= n; i++) val[i] = -val[i]; fill(dp[0],dp[n+1],inf); dfs(1,-1); printf("%dn",-gao()); } return 0;}
