Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> adj[100009];
- vector<bool> visited(100009,false);
- vector<int> contains(100009,0);
- int ans,m;
- void dfs(int source,int val){
- if(adj[source].size()==1&&source!=1&&val+contains[source]>m) //calculating how many leaf nodes are having consecutive cats>m
- { //cout<<"if fired: "<<source<<endl;
- ans--;}
- if(!contains[source])
- val=0;
- else
- val++;
- visited[source]=true;
- for(auto i:adj[source])
- if(!visited[i]){
- dfs(i,val);
- }
- }
- int main() {
- // your code goes here
- int n; cin>>n>>m;
- for(int i=1;i<=n;i++)
- cin>>contains[i];
- for(int i=0;i<n-1;i++){
- int a,b;
- cin>>a>>b;
- adj[a].push_back(b);
- adj[b].push_back(a);
- }
- ans=0;
- for(int i=2;i<=n;i++)
- if(adj[i].size()==1) //calculating total no.of leaf nodes;
- ans++;
- dfs(1,0);
- cout<<ans<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment