fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "0"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16. #define LOG 20
  17.  
  18. const ll MAX=5e5+5;
  19. int n,q;
  20. vector<int> adj[MAX];
  21.  
  22. //hld
  23. int par[MAX],heavy[MAX],h[MAX],treeSize[MAX];
  24. void dfs1(int u, int p)
  25. {
  26.     treeSize[u]=1;
  27.     int mx=0;
  28.     for(int v:adj[u])
  29.     {
  30.         if(v==p) continue;
  31.         par[v]=u;
  32.         h[v]=h[u]+1;
  33.         dfs1(v,u);
  34.         treeSize[u]+=treeSize[v];
  35.         if(treeSize[v]>mx)
  36.         {
  37.             mx=treeSize[v];
  38.             heavy[u]=v;
  39.         }
  40.     }
  41. }
  42. int pos[MAX],head[MAX],cur=0;
  43. void dfs2(int u, int p)
  44. {
  45.     head[u]=p;
  46.     pos[u]=++cur;
  47.     if(heavy[u]!=0) dfs2(heavy[u],p);
  48.     for(int v:adj[u])
  49.     {
  50.         if(v!=par[u] && v!=heavy[u]) dfs2(v,v);
  51.     }
  52. }
  53. void buildHLD()
  54. {
  55.     dfs1(1,0);
  56.     dfs2(1,1);
  57. }
  58.  
  59. //segtree
  60. int st[4*MAX],lazy[4*MAX];
  61. void Push(int u, int l, int r)
  62. {
  63.     if(lazy[u]==-1) return;
  64.     st[u]=lazy[u];
  65.     if(l!=r)
  66.     {
  67.         lazy[u<<1]=lazy[u];
  68.         lazy[u<<1|1]=lazy[u];
  69.     }
  70.     lazy[u]=-1;
  71.     return;
  72. }
  73. void update(int u, int l, int r, int ul, int ur, int val)
  74. {
  75.     if(ul>ur) return;
  76.     Push(u,l,r);
  77.     if(l>ur || r<ul) return;
  78. //    cout<<u<<' '<<l<<' '<<r<<' '<<lazy[u]<<el;
  79.     if(ul<=l&&r<=ur)
  80.     {
  81.         st[u]=val;
  82.         lazy[u]=val;
  83.         if(l!=r)
  84.         {
  85.             lazy[u<<1]=val;
  86.             lazy[u<<1|1]=val;
  87.         }
  88. //        cout<<"OK\n"<<u<<' '<<l<<' '<<r<<' '<<st[u]<<el;
  89.         return;
  90.     }
  91.     int mid=(l+r)>>1;
  92.     update(u<<1,l,mid,ul,ur,val); update(u<<1|1,mid+1,r,ul,ur,val);
  93. }
  94. int query(int u, int l, int r, int pos)
  95. {
  96.     Push(u,l,r);
  97. //    cout<<u<<' '<<l<<' '<<r<<' '<<lazy[u]<<el;
  98.     if(l==r)
  99.     {
  100.         return st[u];
  101.     }
  102.     int mid=(l+r)>>1;
  103.     if(pos<=mid) return query(u<<1,l,mid,pos);
  104.     return query(u<<1|1,mid+1,r,pos);
  105. }
  106.  
  107. void updateAncestor(int u)
  108. {
  109.     while(u!=0)
  110.     {
  111. //        cout<<pos[head[u]]<<' '<<pos[u]<<el;
  112.         update(1,1,n,pos[head[u]],pos[u],0);
  113.         u=par[head[u]];
  114.     }
  115. }
  116.  
  117. int main()
  118. {
  119.     fastio
  120.     if(fopen(FILE ".inp","r"))
  121.     {
  122.         freopen(FILE ".inp","r",stdin);
  123.         freopen(FILE ".out","w",stdout);
  124.     }
  125.     cin>>n;
  126.     foru(i,1,n-1)
  127.     {
  128.         int u,v; cin>>u>>v;
  129.         adj[u].pb(v);
  130.         adj[v].pb(u);
  131.     }
  132.     buildHLD();
  133.     cin>>q;
  134.     while(q--)
  135.     {
  136.         int c,v; cin>>c>>v;
  137.         if(c==1)
  138.         {
  139.             update(1,1,n,pos[v],pos[v]+treeSize[v]-1,1);
  140. //            foru(i,1,n) cout<<query(1,1,n,pos[i])<<' ';
  141. //            cout<<el;
  142.         }
  143.         else if(c==2) updateAncestor(v);
  144.         else cout<<query(1,1,n,pos[v])<<el;
  145.     }
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0.01s 22192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lzGIp2
language:
C++14 (gcc 8.3)
created:
1 hour 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!