Facebook
From Colorant Dormouse, 5 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 177
  1. #include <bits/stdc++.h>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <iostream>
  6. #define MAXN 500001
  7.  
  8. using namespace std;
  9.  
  10. vector <int> synowie[MAXN];
  11. vector <int> galezie[MAXN];
  12. int ojciec[MAXN];
  13. bitset <MAXN> odw;
  14. bitset <MAXN> strajk;
  15.  
  16. void dfs(int x)
  17. {
  18.     odw[x] = true;
  19.  
  20.     for(int i = 0; i < galezie[x].size(); i++)
  21.             if(galezie[x][i] != ojciec[x]) synowie[x].push_back(galezie[x][i]);
  22.  
  23.     for(int i = 0; i < (int) synowie[x].size(); i++)
  24.         if(!odw[synowie[x][i]])
  25.         {
  26.             ojciec[synowie[x][i]] = x;
  27.             dfs(synowie[x][i]);
  28.         }
  29. }
  30.  
  31. int main()
  32. {
  33.     int n, x, y, m, pomoc_strajki;
  34.     int wynik = 1;
  35.  
  36.     scanf("%d",&n);
  37.  
  38.     for(int i = 1; i < n; i++)
  39.     {
  40.         scanf("%d%d",&x,&y);
  41.  
  42.         galezie[x].push_back(y);
  43.         galezie[y].push_back(x);
  44.     }
  45.  
  46.     dfs(1);
  47.  
  48.     scanf("%d",&m);
  49.  
  50.     for(int i = 0; i < m; i++)
  51.     {
  52.         scanf("%d",&pomoc_strajki);
  53.         if(pomoc_strajki > 0) strajk[pomoc_strajki].flip();
  54.             else strajk[pomoc_strajki * -1].flip();
  55.  
  56.         if(pomoc_strajki > 0)
  57.         {
  58.             if(!strajk[ojciec[pomoc_strajki]]) wynik++;
  59.  
  60.             for(int j = 0; j < synowie[ojciec[pomoc_strajki]].size(); j++)
  61.                 if(synowie[ojciec[pomoc_strajki]][j] == pomoc_strajki)
  62.                     synowie[ojciec[pomoc_strajki]].erase(synowie[ojciec[pomoc_strajki]].begin()+j);
  63.  
  64.             wynik += synowie[pomoc_strajki].size();
  65.  
  66.             wynik--;
  67.         }
  68.  
  69.         if(pomoc_strajki < 0)
  70.         {
  71.             if(!strajk[ojciec[-1 * pomoc_strajki]]) wynik--;
  72.  
  73.             synowie[ojciec[-1 * pomoc_strajki]].push_back(-1 * pomoc_strajki);
  74.  
  75.             wynik -= synowie[-1 * pomoc_strajki].size();
  76.  
  77.             wynik++;
  78.         }
  79.  
  80.         printf("%d\n",wynik);
  81.     }
  82. }
  83.