fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 1000001
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<30)
  16. #define BLOCK 425
  17. #define NAME "file"
  18. #define debug(a) cout << #a << " = " << a << endl;
  19. using namespace std;
  20.  
  21. ll n, m, q ;
  22. ll c[MAXN] ;
  23. ll cnt[MAXN ] ;
  24. ll freg[MAXN ] ;
  25. ll res[MAXN ] ;
  26. ll st[MAXN ], fin[MAXN ], tour[MAXN ], timeDfs ;
  27.  
  28. vector<ll> adj[MAXN ] ;
  29.  
  30. void addC(ll color ) {
  31.     cnt[color ] ++ ;
  32.     freg[cnt[color]] ++ ;
  33. }
  34.  
  35. void delC(ll color ) {
  36.     freg[cnt[color]] -- ;
  37.     cnt[color] -- ;
  38. }
  39.  
  40. struct Data {
  41.     ll l, r, k, id ;
  42.     bool operator < (const Data & other ) const {
  43.         ll A = l / BLOCK, B = other.l / BLOCK ;
  44.         if(A == B ) return (A % 2 == 0 ? r < other.r : r > other.r ) ;
  45.         return A < B ;
  46.     }
  47. };
  48. vector<Data> que ;
  49.  
  50. void dfs(ll u, ll p ) {
  51.     st[u] = ++ timeDfs ;
  52.     tour[timeDfs ] = u ;
  53.     for(ll v : adj[u]) if(v != p ) {
  54.             dfs(v, u ) ;
  55.         }
  56.     fin[u] = timeDfs ;
  57. }
  58.  
  59. void init() {
  60.     cin >> n >> q ;
  61.     FOR(i, 1, n ) cin >> c[i] ;
  62.     FOR(i, 2, n ) {
  63.         ll x, y ;
  64.         cin >> x >> y ;
  65.         adj[x].push_back(y) ;
  66.         adj[y].push_back(x) ;
  67.     }
  68. }
  69.  
  70. void solve() {
  71.     dfs(1 , 1 ) ;
  72.  
  73.     FOR(cnt , 1 , q ) {
  74.     ll x , k ; cin >> x >> k ;
  75.     que.push_back({st[x] , fin[x] , k , cnt }) ;
  76.     }
  77.     sort(que.begin() , que.end() ) ;
  78.     ll l = 1 , r = 0 ;
  79.     for(auto [l1 , r1 , k , id ] : que ) {
  80.  
  81.         while(r < r1 ) addC(c[tour[ ++ r]] ) ;
  82.         while(l > l1 ) addC(c[tour[-- l ]] ) ;
  83.  
  84.         while(l < l1 ) delC(c[tour[l ++ ]] ) ;
  85.         while(r > r1 ) delC(c[tour[r -- ]] ) ;
  86.         res[id] = freg[k] ;
  87.     }
  88.  
  89.     FOR(i, 1, q ) cout << res[i] << el ;
  90. }
  91.  
  92.  
  93. _ROOT_ {
  94. //    freopen(NAME".inp", "r", stdin);
  95. //    freopen(NAME".out", "w", stdout) ;
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.     cout.tie(0);
  99.     int t = 1; // cin >> t ;
  100.     while(t--) {
  101.         init();
  102.         solve();
  103.     }
  104.     return (0&0);
  105. }
  106.  
Success #stdin #stdout 0.01s 33104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8USY8K
language:
C++14 (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!