fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXL = 20;
  5.  
  6. int n, q;
  7. vector<vector<int>> g;
  8. int up[MAXL+1][400005+5], depth_[400005+5], tin[400005+5], tout[400005+5], revv[400005+5], sz[400005+5], topc[400005+5];
  9. int timer_;
  10.  
  11. void dfs(int u, int p, int topid){
  12.     up[0][u]=p;
  13.     topc[u]=topid;
  14.     depth_[u]= (p? depth_[p]+1:0);
  15.     tin[u]=++timer_; revv[tin[u]]=u; sz[u]=1;
  16.     for(int v: g[u]){
  17.         if(v==p) continue;
  18.         if(u==1) dfs(v,u,v);
  19.         else dfs(v,u,topid);
  20.         sz[u]+=sz[v];
  21.     }
  22.     tout[u]=timer_;
  23. }
  24.  
  25. int lca(int a, int b){
  26.     if(depth_[a]<depth_[b]) swap(a,b);
  27.     int d = depth_[a]-depth_[b];
  28.     for(int k=0;k<=MAXL;k++) if(d&(1<<k)) a = up[k][a];
  29.     if(a==b) return a;
  30.     for(int k=MAXL;k>=0;k--){
  31.         if(up[k][a]!=up[k][b]){
  32.             a=up[k][a];
  33.             b=up[k][b];
  34.         }
  35.     }
  36.     return up[0][a];
  37. }
  38.  
  39. int main(){
  40.     //freopen("stalingrad.inp","r",stdin);
  41.     //freopen("stalingrad.out","w",stdout);
  42.     ios::sync_with_stdio(false);
  43.     cin.tie(nullptr);
  44.  
  45.     int theta; 
  46.     if(!(cin>>theta)) return 0;
  47.     cin>>n>>q;
  48.     g.assign(n+1,{});
  49.     for(int i=2;i<=n;i++){
  50.         int p; cin>>p;
  51.         g[p].push_back(i);
  52.         g[i].push_back(p);
  53.     }
  54.     dfs(1,0,0);
  55.     for(int k=1;k<=MAXL;k++){
  56.         for(int v=1;v<=n;v++){
  57.             up[k][v]=up[k-1][ up[k-1][v] ];
  58.         }
  59.     }
  60.  
  61.     vector< set<int> > S(n+1);
  62.     vector<int> cnt(n+1,0);
  63.     vector<long long> f(n+1,0);
  64.     long long isolated=0;
  65.     long long edges=0;
  66.  
  67.     auto recompute = [&](int c){
  68.         long long old = f[c];
  69.         if(cnt[c]==0){ f[c]=0; }
  70.         else{
  71.             int a = revv[*S[c].begin()];
  72.             int b = revv[*S[c].rbegin()];
  73.             int e = lca(a,b);
  74.             f[c] = (long long)sz[e] - cnt[c];
  75.         }
  76.         isolated += f[c]-old;
  77.     };
  78.  
  79.     for(int i=0;i<q;i++){
  80.         char op; int v; 
  81.         cin>>op>>v;
  82.         int c = topc[v];
  83.         if(op=='+'){
  84.             if(cnt[c]==0) edges++;
  85.             cnt[c]++;
  86.             S[c].insert(tin[v]);
  87.             recompute(c);
  88.         }else{
  89.             S[c].erase(tin[v]);
  90.             cnt[c]--;
  91.             if(cnt[c]==0) edges--;
  92.             recompute(c);
  93.         }
  94.         cout<<edges<<" "<<isolated<<"\n";
  95.     }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 42516KB
comments (?)
stdin
copy 
3
10 5
1 2 2 2 1 6 7 7 6
+ 9
+ 7
+ 2
- 9
- 7
stdout
copy 
1 0
1 1
2 4
2 5
1 3
https://ideone.com/TVqcLs
language:
C++14 (clang 8.0)
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!