fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5. #define endme "\n";
  6. #define ffprint(x)        \
  7.     for (auto &i : x)      \
  8.     {                     \
  9.         cout << i << " "; \
  10.     } \
  11.     cout<<endme;
  12. #define vectinput(x) for(auto &i : x) cin >> i;
  13. #ifndef ONLINE_JUDGE
  14.    #include"Debug.cpp"
  15. #endif
  16.  
  17.  
  18. void solve(){
  19.     int n,m;
  20.     cin>>n>>m;
  21.     vector<int>dangerous(n);
  22.     vectinput(dangerous);
  23.     vector<vector<int>> tree(n);
  24.     for(int i=0;i<n-1;i++){
  25.         int a,b;
  26.         cin>>a>>b;
  27.         a--;
  28.         b--;
  29.         tree[a].push_back(b);
  30.     }
  31.  
  32.     vector<int>streak(n),maxstreak(n);
  33.     queue<int>q;
  34.     q.push(0);
  35.     streak[0]=(dangerous[0]?1:0);
  36.     maxstreak[0]=streak[0];
  37.     int ans=0;
  38.     while(!q.empty()){
  39.         int top=q.front();
  40.         q.pop();
  41.         if(tree[top].empty() && (maxstreak[top]<=m)){
  42.             ans++;
  43.         }
  44.         for(auto node:tree[top]){
  45.             if(dangerous[node]){
  46.                 streak[node]=streak[top]+1;
  47.             }else{
  48.                 streak[node]=0;
  49.             }
  50.             maxstreak[node]=max(streak[node],maxstreak[top]);
  51.             q.push(node);
  52.         }
  53.     }
  54.     cout<<ans<<endme;
  55.  
  56. }
  57.  
  58.  
  59. int main() {
  60.     ios::sync_with_stdio(false);
  61.     cin.tie(0);
  62.     cout.tie(0);
  63.     #ifndef ONLINE_JUDGE
  64.         freopen("0-InputFile/input.txt", "r", stdin);
  65.         freopen("0-InputFile/output.txt", "w", stdout);
  66.     #endif
  67.  
  68.    int t;
  69.    cin>>t;
  70. //    t=1;
  71.     while (t--) {
  72.         solve();
  73.     }
  74.     return 0;
  75. }
  76.  
  77. /*
  78. reset_template.bat
  79. %%%%%%%%+++*%@@@@@%%@%%%%%%%%%%%@@%%%%%%##**###%%%
  80. %%%%%%%%#*#%@@@@@@@%%%%%#%%%@@@@@%####**####%%@@@@
  81. %%%%%%%%##%@@@@@@@*+++++++++*#@@@@%####%%%%@@@@@@@
  82. %%%%%%%%#%%@@@@@#++++++++++++@@@@@@@%%%@@@@@@@@@@@
  83. @%#%%#%#%%%%%%*++++++++++++++*@@@@@@#++++++*######
  84. %%%%%#%%%###++++++++++++++++++*#@@@#*******#******
  85. #%%%%%%%%%%*+++++******+++++++++**++*##**+++***##%
  86. %%#%%%%%@@*++++*%@@#*****#%#*++++++++++++**##%@@@%
  87. %%%%%%%%%#+***#@@@#++*++*@@@#***+++++++*#%@@%##%%%
  88. %%%%%%%%#**###%@@#+++++++#@@@#*#**++**##%#####%@@@
  89. %%%%%%%%%**####%#++*##*++*@@@%###***#@@@@@%%%%@@@@
  90. %%%%%%%%%#*#####**#@@@@@***%%%%%##*%@@@@@@@@%%@@%%
  91. %%%%%%%%#%**######%%@@%##%%%%%%%##%@@@@@@@@@%#****
  92. %@@%%%###@@%#%%%@%%@@@@@@@%%%%%%%@@@@@@@@@@@@%#**#
  93. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###
  94. %%%#%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  95. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%
  96. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%
  97. */
  98.  
  99.  
  100.  
  101.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
5 2
1 1 0 1 1
1 2
2 3
3 4
4 5
stdout
copy 
2
1
https://ideone.com/2Zq4i2
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!