fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = 0x3f3f3f3f3f3f3f3f;
  17. const int MAX_N = 2e5;
  18.  
  19. struct Query{
  20.     int l, r, k, id;
  21. };
  22.  
  23. int freq[MAX_N + 5], cnt[MAX_N + 5], bacon[MAX_N + 5], ans[MAX_N + 5];
  24. int tin[MAX_N + 5], tout[MAX_N + 5], pos[MAX_N + 5], timer;
  25. vector<int> g[MAX_N + 5];
  26. Query queries[MAX_N + 5];
  27. pii tmp[MAX_N + 5];
  28. int c[MAX_N + 5];
  29. int Block, Vock;
  30. int n, q;
  31.  
  32. bool cmp(const Query &x, const Query &y){
  33.     if((x.l / Block) != (y.l / Block)) return (x.l / Block) < (y.l / Block);
  34.     if((x.l / Block) & 1) return x.r < y.r;
  35.     return x.r > y.r;
  36. }
  37.  
  38. void Input(){
  39.     cin >> n >> q;
  40.     Vock = max(1LL, (int)sqrt(n));
  41.     Block = max(1LL, (int)sqrt(q));
  42.  
  43.     FOR(i, 1, n) cin >> c[i];
  44.  
  45.     FOR(i, 1, n - 1){
  46.         int u, v;
  47.         cin >> u >> v;
  48.  
  49.         g[u].pb(v);
  50.         g[v].pb(u);
  51.     }
  52.  
  53.     FOR(i, 1, q) cin >> tmp[i].fi >> tmp[i].sec;
  54. }
  55.  
  56. void dfs_euler(int u, int dad){
  57.     tin[u] = ++timer;
  58.     pos[timer] = u;
  59.  
  60.     for(int v : g[u]) if(v != dad){
  61.         dfs_euler(v, u);
  62.     }
  63.  
  64.     tout[u] = timer;
  65. }
  66.  
  67. void Prepare(){
  68.     dfs_euler(1, 0);
  69.  
  70.     FOR(i, 1, q){
  71.         int u = tmp[i].fi, k = tmp[i].sec;
  72.         queries[i] = {tin[u], tout[u], k, i};
  73.     }
  74.     sort(queries + 1, queries + q + 1, cmp);
  75. }
  76.  
  77. void add(int x){
  78.     cnt[freq[x]]--;
  79.     bacon[freq[x] / Vock]--;
  80.  
  81.     freq[x]++;
  82.  
  83.     cnt[freq[x]]++;
  84.     bacon[freq[x] / Vock]++;
  85. }
  86.  
  87. void remo(int x){
  88.     cnt[freq[x]]--;
  89.     bacon[freq[x] / Vock]--;
  90.  
  91.     freq[x]--;
  92.  
  93.     cnt[freq[x]]++;
  94.     bacon[freq[x] / Vock]++;
  95. }
  96.  
  97. int get_ans(int k){
  98.     int res = 0, in_block = k / Vock;
  99.     REP(bucket, n / Vock, in_block + 1) res += bacon[bucket];
  100.     FOR(i, k, min(n, Vock * (in_block + 1) - 1)) res += cnt[i];
  101.     return res;
  102. }
  103.  
  104. void Solve(){
  105.     int tl = 1, tr = 0;
  106.     FOR(i, 1, q){
  107.         int l = queries[i].l, r = queries[i].r;
  108.         int k = queries[i].k, id = queries[i].id;
  109.  
  110.         while(l < tl) add(c[pos[--tl]]);
  111.         while(tr < r) add(c[pos[++tr]]);
  112.         while(tl < l) remo(c[pos[tl++]]);
  113.         while(r < tr) remo(c[pos[tr--]]);
  114.  
  115.         ans[id] = get_ans(k);
  116.     }
  117.     FOR(i, 1, q) cout << ans[i] << el;
  118. }
  119.  
  120. signed main(){
  121.     freopen("tree-random.inp", "r", stdin);
  122.     freopen("tree-random.out", "w", stdout);
  123.     ios_base::sync_with_stdio(0);
  124.     cin.tie(0);
  125.  
  126.     Input();
  127.     Prepare();
  128.     Solve();
  129.  
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0.01s 14124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dECr8t
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!