fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 3e5;
  12.  
  13. struct Edge
  14. {
  15.     int x, y, c;
  16.  
  17.     Edge(int x = 0, int y = 0, int c = 0) : 
  18.         x(x), y(y), c(c) {};
  19. };
  20.  
  21. int subtask, n, q, ans = 0, cnt[4 * maxn + 10];
  22. Edge edges[maxn + 10];
  23. vector<ii> v;
  24. ii query[maxn + 10];
  25.  
  26. int get_id(int x, int color)
  27. {
  28.     return lower_bound(v.begin(), v.end(), ii(x, color)) - v.begin();
  29. }
  30. int get(int id, int color)
  31. {
  32.     int x = edges[id].x;
  33.     int y = edges[id].y;
  34.     int quantity = ((cnt[get_id(x, color)] != 0) + (cnt[get_id(y, color)] != 0));
  35.     if (quantity == 1)
  36.         return 0;
  37.     else if (quantity == 2)
  38.         return -1;
  39.     return 1;
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  45.     if (fopen("TREE-EDGE-COLOR-QUERIES.INP", "r"))
  46.     {
  47.         freopen("TREE-EDGE-COLOR-QUERIES.INP", "r", stdin);
  48.         freopen("TREE-EDGE-COLOR-QUERIES.OUT", "w", stdout);
  49.     }
  50.  
  51.     cin >> subtask;
  52.     cin >> n;
  53.     for (int i = 1; i < n; i++)
  54.     {
  55.         int x, y, c;
  56.         cin >> x >> y >> c;
  57.         edges[i] = Edge(x, y, c);
  58.         v.push_back(ii(x, c));
  59.         v.push_back(ii(y, c));
  60.     }
  61.  
  62.     cin >> q;
  63.     for (int j = 1; j <= q; j++)
  64.     {
  65.         int i, d;
  66.         cin >> i >> d;
  67.         int x = edges[i].x;
  68.         int y = edges[i].y;
  69.         v.push_back(ii(x, d));
  70.         v.push_back(ii(y, d));
  71.         query[j] = ii(i, d);
  72.     }
  73.     sort(v.begin(), v.end());
  74.     v.resize(unique(v.begin(), v.end()) - v.begin());
  75.     for (int i = 1; i < n; i++)
  76.     {
  77.         int x = edges[i].x;
  78.         int y = edges[i].y;
  79.         int color = edges[i].c;
  80.         ans += get(i, color);
  81.         cnt[get_id(x, color)]++;
  82.         cnt[get_id(y, color)]++;
  83.     }
  84.     cout << ans << ' ';
  85.     for (int i = 1; i <= q; i++)
  86.     {
  87.         int id = query[i].fi;
  88.         int d = query[i].se;
  89.         int x = edges[id].x;
  90.         int y = edges[id].y;
  91.         int c = edges[id].c;
  92.         cnt[get_id(x, c)]--;
  93.         cnt[get_id(y, c)]--;
  94.         ans += -get(id, c) + get(id, d);
  95.         cnt[get_id(x, d)]++;
  96.         cnt[get_id(y, d)]++;
  97.         cout << ans << ' ';
  98.         edges[id].c = d;
  99.     }
  100. }
Success #stdin #stdout 0.01s 9808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/wwcHn3
language:
C++14 (gcc 8.3)
created:
8 days 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!