rhuntervk

Untitled

Apr 9th, 2020
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment