Advertisement
MinhNGUYEN2k4

Untitled

Sep 4th, 2021
1,204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 300005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n;
  28. vector<int> a[N];
  29. vector<int> s;
  30. int q, node;
  31. int nn;
  32. int color[N], vst[N];
  33.  
  34. void readfile()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);cout.tie(0);
  38.     if (fopen(Task".inp","r"))
  39.     {
  40.         freopen(Task".inp","r",stdin);
  41.         //freopen(Task".out","w",stdout);
  42.     }
  43.     cin >> n >> q >> node;
  44.     for(int i=1; i<n; i++){
  45.         int u, v;
  46.         cin >> u >> v;
  47.         a[u].pb(v);
  48.         a[v].pb(u);
  49.     }
  50.     for(int i=1; i<=n; i++){
  51.         cin >> color[i];
  52.     }
  53. }
  54.  
  55. int dfs(int u){
  56.     s.pb(u);
  57.     vst[u]=1;
  58.     if (a[u].size()==0)
  59.         return u;
  60.     for(auto v : a[u]){
  61.         if (vst[v]) continue;
  62.         int temp = dfs(v);
  63.         s.pb(temp);
  64.     }
  65.     return u;
  66. }
  67.  
  68. int in[N], ou[N];
  69. bool fir[N];
  70. ii b[N*4];
  71. map<int,int> last;
  72. struct query {
  73.     int u, v, id;
  74.     bool operator < (const query &q) const {
  75.         return u < q.u;
  76.     }
  77. } qry[N];
  78. int bit[N*4];
  79. int ans[N];
  80.  
  81. void increase(int v) {
  82.     for(; v <= nn; v += v & -v) ++bit[v];
  83. }
  84.  
  85. int sum(int v) {
  86.     int res = 0;
  87.     for(; v != 0; v -= v & -v) res += bit[v];
  88.     return res;
  89. }
  90.  
  91. void proc()
  92. {
  93.     s.pb(dfs(node));
  94.     for(int i=0; i<s.size(); i++){
  95.         int x = s[i];
  96.         if (!fir[x]){
  97.             fir[x] = true;
  98.             in[x] = i+1;
  99.         }
  100.         else ou[x] = i+1;
  101.     }
  102.     nn = s.size();
  103.     for(int i=1; i<=nn; i++){
  104.         int x = color[s[i-1]];
  105.         b[i] = make_pair(last[x],i);
  106.         last[x] = i;
  107.     }
  108.     for(int i=1; i<=n; i++){
  109.         qry[i].u = in[i];
  110.         qry[i].v = ou[i];
  111.         qry[i].id = i;
  112.     }
  113.     sort(qry+1,qry+1+n);
  114.     sort(b+1,b+1+nn);
  115.     int p = nn;
  116.     for(int i=n; i>=1; i--){
  117.         query &Q = qry[i];
  118.         while(b[p].first >= Q.u) increase(b[p--].second);
  119.         ans[Q.id] = (Q.v - Q.u + 1) - (sum(Q.v) - sum(Q.u));
  120.     }
  121.     while (q--){
  122.         int S; cin >> S;
  123.         cout << ans[S] << '\n';
  124.     }
  125. }
  126.  
  127. signed main()
  128. {
  129.     readfile();
  130.     proc();
  131.     return 0;
  132. }
  133.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement