Untitled
unknown
c_cpp
a year ago
1.7 kB
2
Indexable
Never
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; typedef long long ll; vector<int>adj[maxn]; bool mark[maxn] , mark2[maxn]; int cnt = 1 , dp[maxn] , par[maxn] , res = 0 , jav , k; #define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) #define pb(x) push_back(x) #define all(x) sort(x.begin() , x.end()) void dbg(){ cerr << endl; } template<typename H, typename... T> void dbg(H h, T... t){ cerr << h << ", "; dbg(t...); } #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__) int get(int nw){ //er(res); if(par[nw] == nw){ if(mark2[nw]){ cnt++; res = max(res , cnt); } // er(res); return res; } else{ if(mark2[par[nw]] && mark2[nw]){ cnt++; res = max(cnt , res); // er(res , cnt , nw+1); } else if(mark2[nw]){ cnt = 1; res = max(cnt , res); } else cnt = 0; par[nw] = get(par[nw]); } //er(res , nw+1); } void dfs(int u){ vector<int> v; mark[u] = true; for(auto w : adj[u]){ if(!mark[w]){ par[w] = u; dfs(w); } if(adj[u].size() == 1){ cnt = 1; res = 0; get(u); if(res <= k) jav++; } } } int main(){ int n; cin >> n >> k; int m = n-1; for(int i = 0 ; i < n ; i++){ int a; cin >> a; if(a == 1) mark2[i] = true; } for(int i = 0 ; i < m ; i++){ int u , v; cin >> u >> v; --u;--v; adj[u].push_back(v); adj[v].push_back(u); } par[0] = 0; dfs(0); cout << jav; return 0; }