fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int N = 100005;
  7.  
  8. vector<int> g[N];
  9.  
  10. int color[N];
  11.  
  12. int sz[N];
  13. int heavy[N];
  14.  
  15. bool big[N];
  16.  
  17. vector<pair<int,int>> query[N];
  18.  
  19. int ans[N];
  20.  
  21. int cntColor[N];
  22.  
  23. struct BIT
  24. {
  25.     int bit[N];
  26.  
  27.     void add(int idx, int val)
  28.     {
  29.         while(idx < N)
  30.         {
  31.             bit[idx] += val;
  32.             idx += idx & -idx;
  33.         }
  34.     }
  35.  
  36.     int sum(int idx)
  37.     {
  38.         int s = 0;
  39.  
  40.         while(idx > 0)
  41.         {
  42.             s += bit[idx];
  43.             idx -= idx & -idx;
  44.         }
  45.  
  46.         return s;
  47.     }
  48.  
  49.     int range(int l, int r)
  50.     {
  51.         return sum(r) - sum(l-1);
  52.     }
  53.  
  54. } fw;
  55.  
  56. void getsz(int u, int p)
  57. {
  58.     sz[u] = 1;
  59.  
  60.     heavy[u] = -1;
  61.  
  62.     int mx = 0;
  63.  
  64.     for(int v : g[u])
  65.     {
  66.         if(v == p) continue;
  67.  
  68.         getsz(v, u);
  69.  
  70.         sz[u] += sz[v];
  71.  
  72.         if(sz[v] > mx)
  73.         {
  74.             mx = sz[v];
  75.             heavy[u] = v;
  76.         }
  77.     }
  78. }
  79.  
  80. void add(int u, int p, int val)
  81. {
  82.     int c = color[u];
  83.  
  84.     int old = cntColor[c];
  85.  
  86.     if(old)
  87.         fw.add(old, -1);
  88.  
  89.     cntColor[c] += val;
  90.  
  91.     int now = cntColor[c];
  92.  
  93.     if(now)
  94.         fw.add(now, +1);
  95.  
  96.     for(int v : g[u])
  97.     {
  98.         if(v == p || big[v]) continue;
  99.  
  100.         add(v, u, val);
  101.     }
  102. }
  103.  
  104. void dfs(int u, int p, bool keep)
  105. {
  106.     for(int v : g[u])
  107.     {
  108.         if(v == p || v == heavy[u]) continue;
  109.  
  110.         dfs(v, u, 0);
  111.     }
  112.  
  113.     if(heavy[u] != -1)
  114.     {
  115.         dfs(heavy[u], u, 1);
  116.  
  117.         big[heavy[u]] = 1;
  118.     }
  119.  
  120.     add(u, p, +1);
  121.  
  122.     for(auto [x, id] : query[u])
  123.     {
  124.         ans[id] = fw.range(x, N-1);
  125.     }
  126.  
  127.     if(heavy[u] != -1)
  128.         big[heavy[u]] = 0;
  129.  
  130.     if(!keep)
  131.     {
  132.         add(u, p, -1);
  133.     }
  134. }
  135.  
  136. signed main()
  137. {
  138.     ios::sync_with_stdio(false);
  139.     cin.tie(nullptr);
  140.  
  141.     int n, q;
  142.  
  143.     cin >> n >> q;
  144.  
  145.     for(int i = 1; i <= n; i++)
  146.         cin >> color[i];
  147.  
  148.     for(int i = 1; i < n; i++)
  149.     {
  150.         int u, v;
  151.  
  152.         cin >> u >> v;
  153.  
  154.         g[u].push_back(v);
  155.         g[v].push_back(u);
  156.     }
  157.  
  158.     for(int i = 1; i <= q; i++)
  159.     {
  160.         int u, x;
  161.  
  162.         cin >> u >> x;
  163.  
  164.         query[u].push_back({x, i});
  165.     }
  166.  
  167.     getsz(1, 0);
  168.  
  169.     dfs(1, 0, 1);
  170.  
  171.     for(int i = 1; i <= q; i++)
  172.     {
  173.         cout << ans[i] << '\n';
  174.     }
  175. }
Success #stdin #stdout 0.01s 11724KB
comments (?)
stdin
copy 
4 3
1 2 2 2
1 2
2 3
2 4
1 2
1 1
2 3
stdout
copy 
1
2
1
https://ideone.com/NpzauT
language:
C++14 (clang 8.0)
created:
20 hours 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!