SHARE
TWEET

Untitled

a guest Jun 17th, 2018 154 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top