fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define FOR(i,l,r) for(int i = l; i<= r; i++)
  5. #define fastIO ios::sync_with_stdio(0);cout.tie(0);cin.tie(0)
  6. #define FORD(i,r,l) for(int i = r; i >=l ; i--)
  7. #define LINF 0x3f3f3f3f3f3f3f3f
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define pii pair<int,int>
  12. int n,q;
  13. vector<int> a;
  14. vector<int> g[200005];
  15. int cnt[200005];
  16. bool check[200005];
  17. vector<multiset<int>> sack;
  18. void dfs(int u,int p){
  19.    sack[u].insert(a[u]);
  20.    for(int x : g[u]){
  21.     if(x==p) continue;
  22.     dfs(x,u);
  23.       for(int y : sack[x]){
  24.         sack[u].insert(y);
  25.       }
  26.    }
  27. }
  28. int sol(int u,int x){
  29. memset(check,false,sizeof check);
  30. memset(cnt, 0, sizeof cnt);
  31. int ans =0;
  32. for(int cl : sack[u]){
  33.       cnt[cl]++;
  34.       if(cnt[cl] >= x && !check[cl]){
  35.         ans++;
  36.         check[cl] = true;
  37.       }
  38.    }
  39.    return ans;
  40. }
  41. int main(){
  42. fastIO;
  43. cin>>n>>q;
  44. a.resize(n+1);
  45. sack.resize(n+1);
  46. FOR(i,1,n) cin>>a[i];
  47. FOR(i,1,n-1){
  48.    int x,y;
  49.    cin>>x>>y;
  50.    g[x].pb(y);
  51.    g[y].pb(x);
  52.   }
  53.   dfs(1,-1);
  54.   while(q--){
  55.     int u,x;
  56.     cin>>u>>x;
  57.     cout<<sol(u,x)<<endl;
  58.   }
  59. }
  60.  
Success #stdin #stdout 0.01s 9088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DPlyum
language:
C++ (gcc 8.3)
created:
10 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!