SHARE
TWEET

Untitled

rhuntervk Apr 9th, 2020 5 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n,m;
  7.     cin>>n>>m;
  8.     set<int> s;
  9.     for(int i=1; i<=n; i++)
  10.         s.insert(i);
  11.     vector<int> c(n+1);
  12.     for(int i=1; i<=n; i++)
  13.     {
  14.         cin>>c[i];
  15.         //if(c[i]==1)
  16.             //s.erase(i);
  17.     }
  18.  
  19.     vector<vector<int>> l;
  20.     for(int i=0; i<=n; i++)
  21.     {
  22.         vector<int> t;
  23.         l.push_back(t);
  24.     }
  25.  
  26.     for(int i=1; i<n; i++)
  27.     {
  28.         int u,v;
  29.         cin>>u>>v;
  30.         l[u].push_back(v);
  31.         s.erase(u);
  32.     }
  33.  
  34.     int d[n+1];
  35.     int v[n+1];
  36.  
  37.     for(int i=1; i<=n; i++)
  38.     {
  39.         d[i] = INT_MAX;
  40.         v[i] = 0;
  41.     }
  42.  
  43.     if(c[1]==0)
  44.         d[1] = 0;
  45.     else
  46.         d[1] = 1;
  47.  
  48.     queue<int> q;
  49.     q.push(1);
  50.  
  51.     while(q.size()!=0)
  52.     {
  53.         int x = q.front();
  54.         q.pop();
  55.         v[x] = 1;
  56.         for(int i=0; i<l[x].size(); i++)
  57.         {
  58.             int y = l[x][i];
  59.             if(v[y]==0)
  60.             {
  61.                 q.push(y);
  62.                 if(d[x]==m+1)
  63.                 {
  64.                     d[y] = m+1;
  65.                     continue;
  66.                 }
  67.                 if(c[x]!=0)
  68.                     d[y] = d[x] + c[y];
  69.                 else
  70.                     d[y] = c[y];
  71.             }
  72.         }
  73.     }
  74.  
  75.     int count = 0;
  76.     for(auto i=s.begin(); i!=s.end(); i++)
  77.     {
  78.         int l = *i;
  79.         if(d[l]<=m)
  80.             count++;
  81.     }
  82.     cout<<count<<endl;
  83.     return 0;
  84. }
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