Paste Search Dynamic
Recent pastes
DFS
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. const int MAX=500000;
  6. int n,q,x,y,cnt=0,num[MAX+5];
  7. vector <int> e[MAX+5];
  8. typedef pair <int,int> ii;
  9. ii vis[MAX+5];
  10. struct TP{ ii val; int lazy;};
  11. TP st[MAX*4+5];
  12. void down(int id){
  13.     long long t=st[id].lazy;
  14.     st[id*2].val.fi+=t;
  15.     st[id*2].lazy+=t;
  16.     st[id*2+1].val.fi+=t;
  17.     st[id*2+1].lazy+=t;
  18.     st[id].lazy=0;
  19. }
  20. void update(int id, int l, int r, int u, int v, int val){
  21.     if (r<u || v<l) return;
  22.     if (u<=l && r<=v){
  23.         st[id].val.fi+=val;
  24.         st[id].lazy+=val;
  25.         return;
  26.     }
  27.     down(id);
  28.     int mid=(l+r)/2;
  29.     update(id*2,l,mid,u,v,val); update(id*2+1,mid+1,r,u,v,val);
  30.     st[id].val.se=st[id*2].val.se;
  31.     if (st[id*2].val.fi==st[id*2+1].val.fi){
  32.         st[id].val.se+=st[id*2+1].val.se;
  33.     }
  34.     else{
  35.         if (st[id*2].val.fi>st[id*2+1].val.fi){
  36.             st[id].val.se=st[id*2+1].val.se;
  37.         }
  38.     }
  39.     st[id].val.fi=min(st[id*2].val.fi,st[id*2+1].val.fi);
  40. }
  41. ii get(int id, int l, int r, int u, int v){
  42.     if (r<u || v<l) return ii(1e9,0);
  43.     if (u<=l && r<=v){
  44.         return st[id].val;
  45.     }
  46.     down(id);
  47.     int mid=(l+r)/2;
  48.     ii lchild=get(id*2,l,mid,u,v);
  49.     ii rchild=get(id*2+1,mid+1,r,u,v);
  50.     if (lchild.fi==rchild.fi) return ii(lchild.fi,lchild.se+rchild.se);
  51.     if (lchild.fi<rchild.fi) return ii(lchild.fi,lchild.se);
  52.     return ii(rchild.fi,rchild.se);
  53. }
  54. void build(int id, int l, int r){
  55.     if (l>r) return;
  56.     st[id].val.se=r-l+1;
  57.     if (l==r) return;
  58.     int mid=(l+r)/2;
  59.     build(id*2,l,mid); build(id*2+1,mid+1,r);
  60. }
  61. void DFS(int u,int pa){
  62.     cnt++;
  63.     vis[u].fi=cnt;
  64.     for (int i=0; i<e[u].size(); i++){
  65.         int v=e[u][i];
  66.         if (v!=pa){
  67.             DFS(v,u);
  68.         }
  69.     }
  70.     vis[u].se=cnt;
  71. }
  72. int main(){
  73.     /*freopen("test.inp","r",stdin);
  74.     freopen("test.out","w",stdout);*/
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.     cin>>n>>q;
  77.     for (int i=1; i<n; i++){
  78.         cin>>x>>y;
  79.         e[x].push_back(y);
  80.         e[y].push_back(x);
  81.         num[i]=-1;
  82.     }
  83.     num[n]=-1;
  84.     DFS(1,-1);
  85.     build(1,1,n);
  86.     while(q--){
  87.         cin>>x>>y;
  88.         if (x==1){
  89.             num[y]*=-1;
  90.             update(1,1,n,vis[y].fi,vis[y].se,num[y]);
  91.         }
  92.         else{
  93.             if (num[y]==1) cout<<0<<"n";
  94.             else{
  95.                 cout<<get(1,1,n,vis[y].fi,vis[y].se).se<<"n";
  96.             }
  97.         }
  98.     }
  99. }
  100.  
Parsed in 0.014 seconds