fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 210000
  7. #define fi first
  8. #define se second
  9. using namespace std;
  10. vector<int> adj[maxn];
  11. ll color[maxn],n,q,ans[maxn],bit[maxn],r;
  12. pair<pair<ll,ll>,ll> query[maxn];
  13. int in[maxn],out[maxn],euler[2*maxn],cnt=0;
  14. void dfs(int u,int p){
  15.    in[u]=++cnt;
  16.    euler[cnt]=color[u];
  17.    for(int v : adj[u]){
  18.       if(v!=p) dfs(v,u);
  19.    }
  20.    out[u]=cnt;
  21. }
  22. void update(int pos,int val){
  23.    for(; pos<maxn;pos += pos & -pos) bit[pos]+=val;
  24. }
  25. bool cmp(pair<pair<ll,ll>,ll> c,pair<pair<ll,ll>,ll> d){
  26.     return c.fi.fi>d.fi.fi;
  27. }
  28. ll get(ll pos){
  29.    ll res=0;
  30.    for(;pos>0; pos-=pos&-pos){
  31.       res+=bit[pos];
  32.    }
  33.    return res;
  34. }
  35. int main()
  36. {
  37.     itachi
  38.     freopen("coltree.inp","r",stdin);
  39.     freopen("coltree.out","w",stdout);
  40.     cin>>n>>q>>r;
  41.     for(int i=1;i<n;i++){
  42.         int u,v; cin>>u>>v;
  43.         adj[u].push_back(v);
  44.         adj[v].push_back(u);
  45.     }
  46.     for(int i=1;i<=n;i++) cin>>color[i];
  47.     dfs(r,-1);
  48.     for(int i=1;i<=q;i++){
  49.         int s; cin>>s;
  50.         query[i]=make_pair(make_pair(in[s],out[s]),i);
  51.     }
  52.     sort(query+1,query+q+1,cmp);
  53.     unordered_map<ll,ll> last;
  54.     int cur=1;
  55.     for(int i=1;i<=cnt;i++) bit[i]=0;
  56.     for(int i=cnt;i>=1;i--){
  57.         ll col=euler[i];
  58.         if(last.count(col)) update(last[col],-1);
  59.         update(i,1);
  60.         last[col]=i;
  61.         while(cur<=q && query[cur].fi.fi ==i){
  62.             int l=query[cur].fi.fi;
  63.             int r=query[cur].fi.se;
  64.             int id=query[cur].se;
  65.             ans[id]=get(r)-get(l-1);
  66.             ++cur;
  67.         }
  68.     }
  69.     for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 11808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o6zPvr
language:
C++14 (gcc 8.3)
created:
3 days 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!