#include <bits/stdc++.h>
using namespace std ;
#define int long long
bool v[100003] ;
vector <int> adj[100003] ;
int n,k ;
int arr[100003] ;
int tt=0 ;
int sz[100003] ;
void dfs(int x){
v[x]=1 ;
vector <int> vv ;
int ttt=arr[x] ;
for (auto a : adj[x]){
if (v[a]) continue ;
dfs(a) ;
vv.push_back(sz[a]) ;
ttt+=sz[a] ;
}
sort(vv.begin(),vv.end()) ;
int i=vv.size()-1 ;
while (ttt>k){
ttt-=vv[i] ;
tt++ ;
i-- ;
}
sz[x]=ttt ;
}
signed main(){
int i,j ;
cin >> n >> k ;
for (i = 1 ; i <= n ; i ++) cin >> arr[i] ;
for (i = 0 ; i < n-1 ; i ++){
int a,b ;
cin >> a >> b ;
adj[a].push_back(b) ;
adj[b].push_back(a) ;
}
dfs(1) ;
cout << tt << endl ;
return 0 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |