SHARE
TWEET

Untitled

a guest Jan 28th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int n,m;
  7.  
  8. vector <int> sas[1000000+5];
  9. vector <int> synowie[1000000+5];
  10. int father[1000000+5];
  11. int zabl_syn[1000000+5];
  12. bool zabl[1000000+5];
  13. bool odw[1000000+5];
  14.  
  15. int result = 1;
  16.  
  17. void DFS(int w)
  18. {
  19.     odw[w] = 1;
  20.     int s = sas[w].size();
  21.     for(int i=0; i<s; i++)
  22.         if(!odw[sas[w][i]])
  23.         {
  24.             father[sas[w][i]] = w;
  25.             synowie[w].push_back(sas[w][i]);
  26.             DFS(sas[w][i]);
  27.         }
  28. }
  29.  
  30. inline void DELETE(int w)
  31. {
  32.     int liczba = 1;
  33.     if(!zabl[father[w]]) /// jesli ojciec nie jesy zablokowany
  34.         liczba--;
  35.  
  36.     liczba -= (synowie[w].size() - zabl_syn[w]);
  37.  
  38.     result += liczba;
  39.     zabl[w] = 0;
  40.     zabl_syn[father[w]]--;
  41. }
  42.  
  43. inline void ADD(int w)
  44. {
  45.     int liczba = -1;
  46.     zabl[w] = 1;
  47.     zabl_syn[father[w]]++;
  48.  
  49.     if(!zabl[father[w]])
  50.         liczba++;
  51.  
  52.     liczba += (synowie[w].size() - zabl_syn[w]);
  53.     result += liczba;
  54. }
  55.  
  56. int main()
  57. {
  58.     ios_base::sync_with_stdio(0);
  59.     cin.tie(0);
  60.     cin>>n;
  61.     int tmp1, tmp2;
  62.     for(int i=1; i<n; i++)
  63.     {
  64.         cin>>tmp1>>tmp2;
  65.         sas[tmp1].push_back(tmp2);
  66.         sas[tmp2].push_back(tmp1);
  67.     }
  68.  
  69.     father[1] = 0;
  70.     zabl[0] = true;
  71.  
  72.     DFS(1);
  73.  
  74.     int Q;
  75.     cin>>Q;
  76.  
  77.     for(int test=1; test<=Q; test++)
  78.     {
  79.         cin>>tmp1;
  80.         if(tmp1 < 0)
  81.             DELETE(-tmp1);
  82.  
  83.         else
  84.             ADD(tmp1);
  85.         cout<<result<<'\n';
  86.     }
  87.  
  88.     return 0;
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top