Guest User

Untitled

a guest
Jun 17th, 2018
499
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> adj[100009];
  4. vector<bool> visited(100009,false);
  5. vector<int> contains(100009,0);
  6. int ans,m;
  7. void dfs(int source,int val){
  8. if(adj[source].size()==1&&source!=1&&val+contains[source]>m) //calculating how many leaf nodes are having consecutive cats>m
  9. { //cout<<"if fired: "<<source<<endl;
  10. ans--;}
  11. if(!contains[source])
  12. val=0;
  13. else
  14. val++;
  15. visited[source]=true;
  16. for(auto i:adj[source])
  17. if(!visited[i]){
  18. dfs(i,val);
  19. }
  20. }
  21.  
  22. int main() {
  23. // your code goes here
  24. int n; cin>>n>>m;
  25. for(int i=1;i<=n;i++)
  26. cin>>contains[i];
  27. for(int i=0;i<n-1;i++){
  28. int a,b;
  29. cin>>a>>b;
  30. adj[a].push_back(b);
  31. adj[b].push_back(a);
  32. }
  33. ans=0;
  34. for(int i=2;i<=n;i++)
  35. if(adj[i].size()==1) //calculating total no.of leaf nodes;
  36. ans++;
  37. dfs(1,0);
  38. cout<<ans<<endl;
  39. return 0;
  40. }
Add Comment
Please, Sign In to add comment