fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,q,timer=0,a[400005],tin[400005],tout[400005],arr[800005],bit[67][800005];
  4. vector <int> ve[400005];
  5. void DFS(int u, int p)
  6. {
  7.     tin[u]=++timer;
  8.     for (int v : ve[u]) if (v!=p) DFS(v,u);
  9.     tout[u]=++timer;
  10. }
  11. void UPDATE(int id, int i, int v)
  12. {
  13.     while (i<=timer) bit[id][i]+=v,i+=i&(-i);
  14.     return;
  15. }
  16. int GET(int id, int l, int r)
  17. {
  18.     l--;
  19.     int resl=0,resr=0;
  20.     while (l>0) resl+=bit[id][l],l-=l&(-l);
  21.     while (r>0) resr+=bit[id][r],r-=r&(-r);
  22.     return resr-resl;
  23. }
  24. signed main()
  25. {
  26.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  27.     cin>>n>>q;
  28.     for (int i=1;i<=n;i++) cin>>a[i];
  29.     for (int i=1;i<n;i++)
  30.     {
  31.         int u,v;
  32.         cin>>u>>v;
  33.         ve[u].push_back(v),ve[v].push_back(u);
  34.     }
  35.     DFS(1,0);
  36.     for (int i=1;i<=n;i++) UPDATE(a[i],tin[i],1),UPDATE(a[i],tout[i],1);
  37.     for (int i=1;i<=q;i++)
  38.     {
  39.         int t;
  40.         cin>>t;
  41.         if (t==1)
  42.         {
  43.             int u,c;
  44.             cin>>u>>c;
  45.             UPDATE(a[u],tin[u],-1),UPDATE(a[u],tout[u],-1);
  46.             a[u]=c,UPDATE(c,tin[u],1),UPDATE(c,tout[u],1);
  47.         }
  48.         else
  49.         {
  50.             int pa,ans=0;
  51.             cin>>pa;
  52.             for (int i=1;i<=60;i++) if (GET(i,tin[pa],tout[pa])>0) ans++;
  53.             cout<<ans<<'\n';
  54.         }
  55.     }
  56.     return 0;
  57. }
Success #stdin #stdout 0.01s 18016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bZt2dA
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!