Guest User

Untitled

a guest
Jun 19th, 2017
175
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // <3 Appy!
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. typedef unsigned long long ull;
  5. typedef long long int ll;
  6. typedef vector<long long int> vi;
  7. typedef pair<int,int> pii;
  8. int n,t;
  9. int a[222222], l[222222], r[222222], visit[222222], x[(ll)1e6];
  10. ll res[222222], puf[222222], refe[222222], bound[222222], sum;
  11. vector<pair<pii,int> > w;
  12. vi v[(ll)1e5+9];
  13. ll chu = 0;
  14. int kj[222222];
  15. ll dfs(int x)
  16. {
  17.  
  18.     visit[x] = 1;
  19.     chu++;
  20.     ll k = chu;
  21.     res[k] = x;
  22.     refe[x] = k;
  23.     if(v[x].size() == 0)
  24.     {
  25.         bound[k] = k;
  26.         return (k);
  27.     }
  28.     ll ans = k;
  29.     for(int i=0;i<v[x].size();i++)
  30.     {
  31.         if(visit[v[x][i]] == 0)
  32.         {
  33.             visit[v[x][i]] = 1;
  34.             ans = max(dfs(v[x][i]), ans);
  35.         }
  36.     }
  37.     bound[k] = ans;
  38.     return ans;
  39. }
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  43.     cin>>n>>t;
  44.     ll root;
  45.     for(int i=1;i<=n;i++)
  46.     {
  47.         cin>>a[i];
  48.         if(a[i] == 1)
  49.             root = i;
  50.     }
  51.     for(int i=0;i<n-1;i++)
  52.     {
  53.         ll x,y;
  54.         cin>>x>>y;
  55.         v[x].push_back(y);
  56.         v[y].push_back(x);
  57.     }
  58.     dfs(root);
  59.     ll sq = (ll)sqrtl(n);
  60.     for(int i=0;i<t;i++)
  61.     {
  62.         cin>>l[i]>>kj[i];
  63.         w.push_back(make_pair(pii(refe[l[i]]/sq,bound[l[i]]),i));
  64.     }
  65.     sort(w.begin(),w.end());
  66.     int start = 1;
  67.     int end   = 0;
  68.     int ans = 0;
  69.     for(int i=0;i<t;)
  70.     {
  71.         int j=i;
  72.         while(j<t && w[j].first.first==w[i].first.first) j++;
  73.         for(int k = i; k < j; k++)
  74.         {
  75.             int L = l[w[k].second];
  76.             int R = bound[L];
  77.             int p = kj[w[k].second];
  78.             while(start>L)
  79.             {
  80.                 start --;
  81.                 x[a[res[start]]]++;
  82.                 if(x[a[res[start]]] == p) ans++;
  83.             }
  84.             while(start<L)
  85.             {
  86.                 if(x[a[res[start]]] == p) ans--;
  87.                 x[a[res[start]]]--;
  88.                 start ++;
  89.  
  90.             }
  91.             while(end<R)
  92.             {
  93.                 end ++;
  94.                 x[a[end]]++;
  95.                 if(x[a[res[end]]] == p) ans++;
  96.             }
  97.             while(end>R)
  98.             {
  99.                 if(x[a[res[end]]] == p) ans--;
  100.                 x[a[res[end]]]--;
  101.                 end --;
  102.             }
  103.             puf[w[k].second] = ans;
  104.         }
  105.  
  106.         i=j;
  107.     }
  108.     for(int i=0;i<t;i++)
  109.         cout<<puf[i]<<" \n";
  110.     return 0;
  111. }
RAW Paste Data