fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pb push_back
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define fi first
  9. #define se second
  10. #define getbit(x,k) ((x)&(1<<k))
  11. #define MASK(x) (((1)<<(x))-1)
  12. #define M 20
  13. const ll inf=1e9;
  14. const int maxn=2e5+5,mod=1e18+9;
  15. using namespace std;
  16.  
  17. inline ll bp(ll a){return a*a;}
  18. mt19937_64 rang(chrono::steady_clock::now().time_since_epoch().count());
  19.  
  20.  
  21. int n,A[maxn];
  22. vector<int>eg[maxn];
  23. int old[maxn],ans[maxn];
  24. int tin[maxn],tout[maxn],counter=0;
  25. struct SegTree
  26. {
  27.     int sz;
  28.     vector<int>st;
  29.     SegTree(){}
  30.     SegTree(int sz): sz(sz),st(sz*4+10,0) {}
  31.     void update(int l, int r, int lab, int a, int val)
  32.     {
  33.         if(l==r)
  34.         {
  35.             st[lab]=val;
  36.             return;
  37.         }
  38.         int mid=(l+r)/2;
  39.         if(a<=mid) update(l,mid,lab*2,a,val);
  40.         else update(mid+1,r,lab*2+1,a,val);
  41.         st[lab]=st[lab*2]+st[lab*2+1];
  42.     }
  43.     int get(int l, int r, int lab, int a, int b)
  44.     {
  45.         if(l>b || r<a) return 0;
  46.         if(l>=a && r<=b) return st[lab];
  47.         int mid=(l+r)/2;
  48.         return get(l,mid,lab*2,a,b)+get(mid+1,r,lab*2+1,a,b);
  49.     }
  50. }f;
  51.  
  52. void dfs(int u, int p)
  53. {
  54.     tin[u]=++counter;
  55.     for(int v:eg[u])if(v!=p) dfs(v,u);
  56.     tout[u]=counter;
  57.     if(old[A[u]]!=-1) f.update(1,f.sz,1,tin[old[A[u]]],0);
  58.     f.update(1,f.sz,1,tin[u],1);old[A[u]]=u;
  59.     ans[u]=f.get(1,f.sz,1,tin[u],tout[u]);
  60. }
  61. vector<int>N;
  62. void nen()
  63. {
  64.     sort(N.begin(),N.end());
  65.     N.erase(unique(N.begin(),N.end()),N.end());
  66.     for(int i=1;i<=n;i++)
  67.         A[i]=lower_bound(N.begin(),N.end(),A[i])-N.begin()+1;
  68. }
  69. int main()
  70. {
  71.     cin>>n;
  72.     for(int i=1;i<=n;i++)
  73.     {
  74.         cin>>A[i];
  75.         N.pb(A[i]);
  76.     }
  77.     nen();
  78.     for(int i=1;i<n;i++)
  79.     {
  80.         int a,b;cin>>a>>b;
  81.         eg[a].pb(b);eg[b].pb(a);
  82.     }
  83.     memset(old,-1,sizeof old);
  84.     f=SegTree(n);
  85.     dfs(1,1);
  86.     for(int i=1;i<=n;i++)
  87.         cout<<ans[i]<<' ';
  88. }
  89.  
Runtime error #stdin #stdout 1.57s 2096012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qaQb0O
D-Query VNOI
language:
C++14 (gcc 8.3)
created:
11 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!