fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 500005;
  7. vector<int> adj[MAXN];
  8. int parent[MAXN];
  9. int degree[MAXN];
  10. int striking_children[MAXN];
  11. bool is_striking[MAXN];
  12. int n, m;
  13.  
  14. // Budujemy strukturę drzewa (wyznaczamy rodziców)
  15. void dfs(int u, int p) {
  16.     parent[u] = p;
  17.     for (int v : adj[u]) {
  18.         if (v != p) {
  19.             dfs(v, u);
  20.         }
  21.     }
  22. }
  23.  
  24. int main() {
  25.     // Szybkie wejście/wyjście
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(NULL);
  28.  
  29.     if (!(cin >> n)) return 0;
  30.  
  31.     for (int i = 0; i < n - 1; ++i) {
  32.         int u, v;
  33.         cin >> u >> v;
  34.         adj[u].push_back(v);
  35.         adj[v].push_back(u);
  36.         degree[u]++;
  37.         degree[v]++;
  38.     }
  39.  
  40.     // Ukorzeniamy drzewo w wierzchołku 1
  41.     dfs(1, 0);
  42.  
  43.     cin >> m;
  44.     int components = 1; // Na początku sieć jest spójna
  45.  
  46.     while (m--) {
  47.         int z;
  48.         cin >> z;
  49.         int v = (z > 0 ? z : -z);
  50.         bool starting_strike = (z > 0);
  51.  
  52.         // Obliczamy liczbę aktywnych sąsiadów
  53.         int active_children = (v == 1 ? degree[v] : degree[v] - 1) - striking_children[v];
  54.         int parent_active = (v == 1 || is_striking[parent[v]]) ? 0 : 1;
  55.         int active_neighbors = active_children + parent_active;
  56.  
  57.         if (starting_strike) {
  58.             // Rozpoczyna strajk
  59.             components += (active_neighbors - 1);
  60.             is_striking[v] = true;
  61.             if (v != 1) {
  62.                 striking_children[parent[v]]++;
  63.             }
  64.         } else {
  65.             // Kończy strajk
  66.             components -= (active_neighbors - 1);
  67.             is_striking[v] = false;
  68.             if (v != 1) {
  69.                 striking_children[parent[v]]--;
  70.             }
  71.         }
  72.  
  73.         cout << components << "\n";
  74.     }
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 20912KB
comments (?)
stdin
copy 
7
1 2
2 3
2 4
4 5
4 6
6 7
4
2
7
4 -2
stdout
copy 
3
3
4
3
https://ideone.com/iEUXma
language:
C++14 (gcc 8.3)
created:
4 hours 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!