fork download
copy 
  1. /*
  2. ███████  ██████  ███    ██ ██  ██████ ██   ██ ██   ██ ██   ██
  3. ██      ██    ██ ████   ██ ██ ██      ██   ██ ██   ██ ██   ██
  4. ███████ ██    ██ ██ ██  ██ ██ ██      ███████ ███████ ███████
  5.      ██ ██    ██ ██  ██ ██ ██ ██           ██      ██      ██
  6. ███████  ██████  ██   ████ ██  ██████      ██      ██      ██
  7. */
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11. #define sonic ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. #define endl  "\n"
  13. #define gcd  __gcd
  14. #define all(v) v.begin(),v.end()
  15. #define allr(v) v.rbegin(),v.rend()
  16. #define acc(x) accumulate(all(x),0LL)
  17. #define fixed(n) fixed << setprecision(n)
  18. #define ll long long
  19. #define all(v) v.begin(),v.end()
  20. #define mod 1000000007
  21. #define mx(v) *max_element(all(v))
  22. #define mn(v) *min_element(all(v))
  23. #define mxi(v) max_element(all(v))-v.begin()
  24. #define mni(v) min_element(all(v))-v.begin()
  25. #define cin(vec) for(auto &i : vec) cin >> i
  26. #define cout(vec) for(auto& i : vec) cout << i << " "; cout << '\n';
  27.  
  28. ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
  29.  
  30.  
  31. vector<ll> in, out, dffs;
  32.  
  33. struct query {
  34.     int l, r, k, q_idx, block_idx;
  35.  
  36.     query() {}
  37.  
  38.     int SQ = 320;
  39.  
  40.     query(int _l, int _r, ll _k, int _q_idx) {
  41.         l = _l - 1, r = _r - 1, k = _k, q_idx = _q_idx, block_idx = _l / SQ;
  42.     }
  43.  
  44.     bool operator<(const query &y) const {
  45.         if (block_idx != y.block_idx) {
  46.             return block_idx < y.block_idx;
  47.         }
  48.         return r < y.r;
  49.     }
  50. };
  51.  
  52. vector<ll> col;
  53.  
  54. class MO {
  55. public:
  56.     static const int N = 10000005;
  57.     static const int Q = 300005;
  58.     static const int SQ = 320;
  59.  
  60.     vector<ll> v;
  61.     int mx = 0;
  62.     query queries[Q];
  63.     ll n, q, res = 0, q_ans[Q], f[3000005] = {0}, ff[N] = {0};
  64.  
  65.     MO(vector<ll> &vv, vector<pair<pair<ll, ll>, ll>> &lr) {  // 1 indexed l,r
  66.         q = lr.size(), n = vv.size();
  67.         v = vv;
  68.         for (int i = 0; i < lr.size(); ++i)queries[i] = query(lr[i].first.first, lr[i].first.second, lr[i].second, i);
  69.         mo_process();
  70.     }
  71.  
  72.     void add(int i, ll k) {
  73.         // ff[f[col[v[i]]]]--;
  74.         f[col[v[i]]]++;
  75.         ff[f[col[v[i]]]]++;
  76.     }
  77.  
  78.     void remove(int i, ll k) {
  79.         ff[f[col[v[i]]]]--;
  80.         f[col[v[i]]]--;
  81.         ff[f[col[v[i]]]]++;
  82.  
  83.     }
  84.  
  85.     void mo_process() {
  86.         sort(queries, queries + q);
  87.         int l = 1, r = 0;
  88.         for (int i = 0; i < q; i++) {
  89.             while (r < queries[i].r)add(++r, queries[i].k);
  90.             while (r > queries[i].r)remove(r--, queries[i].k);
  91.             while (l < queries[i].l)remove(l++, queries[i].k);
  92.             while (l > queries[i].l)add(--l, queries[i].k);
  93.             q_ans[queries[i].q_idx] = ff[f[queries[i].k]];
  94.         }
  95.     }
  96.  
  97. };
  98.  
  99. const int N = 1e5 + 5;
  100.  
  101. vector<ll> adj[N];
  102. int timer;
  103.  
  104. void dfs(ll node, ll p) {
  105.     in[node] = timer++;
  106.     dffs[timer] = node;
  107.     for (auto i: adj[node]) {
  108.         if (i == p)continue;
  109.         dfs(i, node);
  110.     }
  111.     out[node] = timer;
  112. }
  113.  
  114. void sonic444() {
  115.     ll n, q;
  116.     cin >> n >> q;
  117.     col.resize(n);
  118.     cin(col);
  119.  
  120.     in.resize(n + 5);
  121.     out.resize(n + 5);
  122.     dffs.resize(n + 5);
  123.     for (int i = 0; i < n - 1; ++i) {
  124.         ll u, v;
  125.         cin >> u >> v;
  126.         adj[u].emplace_back(v);
  127.         adj[v].emplace_back(u);
  128.     }
  129.     dfs(1,0);
  130.     // cout(dffs);
  131.     vector<pair<pair<ll, ll>, ll>> lr;
  132.     for (int i = 0; i < q; ++i) {
  133.         ll s, k;
  134.         cin >> s >> k;
  135.         lr.push_back({{in[s]+1, out[s]}, k});
  136.     }
  137.     MO mo(dffs, lr);
  138.  
  139.     for (int i = 0; i < q; ++i) {
  140.         cout << mo.q_ans[i] << endl;
  141.     }
  142.  
  143.  
  144. }
  145.  
  146. int main() {
  147.     // freopen("input1.txt", "r", stdin);
  148.     //    freopen("output.txt", "w", stdout);
  149.     sonic
  150.     //////////////////////////////////////////////
  151.  
  152.     int t = 1;
  153.     //cin>>t;
  154.     while (t--) {
  155.         sonic444();
  156.     }
  157.     return 0;
  158. }
Success #stdin #stdout 0.03s 116792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/I7US88
language:
C++ (gcc 8.3)
created:
1 day 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!