fork download
copy 
  1. // NA
  2. #include <bits/stdc++.h>
  3. #define BUFFER 5
  4. #define BUFF(x) x + BUFFER
  5. #define N_MAX 100000
  6. #define BLOCKS_MAX 317
  7. using namespace std;
  8. typedef long long int ll;
  9. int n;
  10. struct E {
  11.   int v;
  12.   struct E *next;
  13. } edges[BUFF(N_MAX)];
  14. int edges_ptr;
  15. struct {
  16.   ll animals;
  17.   int l_idx;
  18.   struct E *children;
  19.   bool vps;
  20. } nodes[BUFF(N_MAX)];
  21. struct {
  22.   int animal_idx;
  23.   int until;
  24. } linearized_tree[BUFF(N_MAX)];
  25. int l_ptr;
  26. struct {
  27.   int dirty;
  28.   ll sum;
  29. } blocks[BUFF(BLOCKS_MAX)];
  30. int block_size;
  31. int vps_coverage[BUFF(N_MAX)];
  32. struct E *getEdgesFromPool() { return &edges[edges_ptr++]; }
  33. void addToEdges(int u, int v) {
  34.   struct E *t = getEdgesFromPool();
  35.   t->v = v;
  36.   t->next = nodes[u].children;
  37.   nodes[u].children = t;
  38. }
  39. void linearize(int u) {
  40.   int c_idx = ++l_ptr;
  41.   nodes[u].l_idx = c_idx;
  42.   linearized_tree[c_idx].animal_idx = u;
  43.   struct E *t = nodes[u].children;
  44.   while (t) {
  45.     linearize(t->v);
  46.     t = t->next;
  47.   }
  48.   linearized_tree[c_idx].until = l_ptr;
  49. }
  50. int getBlockNumber(int idx) { return (idx - 1) / block_size + 1; }
  51. int getBlockLeft(int blk_id) { return (blk_id - 1) * block_size + 1; }
  52. int getBlockRight(int blk_id) { return min(l_ptr, block_size * blk_id); }
  53. void removeDirtiness(int blk_id) {
  54.   if (blocks[blk_id].dirty != 0) {
  55.     int blk_l, blk_r;
  56.     blk_l = getBlockLeft(blk_id);
  57.     blk_r = getBlockRight(blk_id);
  58.     blocks[blk_id].sum = 0;
  59.     for (int i = blk_l; i <= blk_r; ++i) {
  60.       vps_coverage[i] += blocks[blk_id].dirty;
  61.       if (vps_coverage[i] == 0)
  62.         blocks[blk_id].sum += nodes[linearized_tree[i].animal_idx].animals;
  63.     }
  64.     blocks[blk_id].dirty = 0;
  65.   }
  66. }
  67. void updateRange(int l, int r, int val) {
  68.   int blk_id, blk_l, blk_r;
  69.   while (l <= r) {
  70.     blk_id = getBlockNumber(l);
  71.     blk_l = getBlockLeft(blk_id);
  72.     blk_r = getBlockRight(blk_id);
  73.     if (l == blk_l && blk_r <= r) {
  74.       blocks[blk_id].dirty += val;
  75.       l = blk_r + 1;
  76.     } else {
  77.       removeDirtiness(blk_id);
  78.       int t_r = min(r, blk_r);
  79.       for (int i = l; i <= t_r; ++i) {
  80.         if (vps_coverage[i] == 1 && val == -1)
  81.           blocks[blk_id].sum += nodes[linearized_tree[i].animal_idx].animals;
  82.         else if (vps_coverage[i] == 0 && val == 1)
  83.           blocks[blk_id].sum -= nodes[linearized_tree[i].animal_idx].animals;
  84.         vps_coverage[i] += val;
  85.       }
  86.       l = t_r + 1;
  87.     }
  88.   }
  89. }
  90. void toggleVPS(int u) {
  91.   int l, r, val;
  92.   if (nodes[u].vps) val = -1;
  93.   else val = 1;
  94.   l = nodes[u].l_idx;
  95.   r = linearized_tree[l].until;
  96.   updateRange(l, r, val);
  97.   nodes[u].vps = !nodes[u].vps;
  98. }
  99. ll getSum(int u) {
  100.   int l = nodes[u].l_idx, r = linearized_tree[l].until;
  101.   int blk_id, blk_l, blk_r;
  102.   ll sum = 0;
  103.   while (l <= r) {
  104.     blk_id = getBlockNumber(l);
  105.     blk_l = getBlockLeft(blk_id);
  106.     blk_r = getBlockRight(blk_id);
  107.     if (l == blk_l && blk_r <= r) {
  108.       if (blocks[blk_id].dirty < 0) {
  109.         removeDirtiness(blk_id);
  110.         sum += blocks[blk_id].sum;
  111.       } else if (blocks[blk_id].dirty == 0)
  112.         sum += blocks[blk_id].sum;
  113.       l = blk_r + 1;
  114.     } else {
  115.       removeDirtiness(blk_id);
  116.       int t_r = min(r, blk_r);
  117.       for (int i = l; i <= t_r; ++i)
  118.         if (vps_coverage[i] == 0)
  119.           sum += nodes[linearized_tree[i].animal_idx].animals;
  120.       l = t_r + 1;
  121.     }
  122.   }
  123.   return sum;
  124. }
  125. void preprocess() {
  126.   int t_r = getBlockNumber(l_ptr);
  127.   int blk_l, blk_r;
  128.   for (int blk_id = 1; blk_id <= t_r; ++blk_id) {
  129.     blk_l = getBlockLeft(blk_id);
  130.     blk_r = getBlockRight(blk_id);
  131.     for (int i = blk_l; i <= blk_r; ++i)
  132.       blocks[blk_id].sum += nodes[linearized_tree[i].animal_idx].animals;
  133.   }
  134. }
  135. void program() {
  136.   int u, v, q;
  137.   scanf("%d", &n);
  138.   block_size = sqrt(n);
  139.   for (int i = 1; i <= n; ++i)
  140.     scanf("%lld", &nodes[i].animals);
  141.   for (int i = 1; i < n; ++i) {
  142.     scanf("%d %d", &u, &v);
  143.     addToEdges(u, v);
  144.   }
  145.   linearize(1);
  146.   preprocess();
  147.   scanf("%d", &q);
  148.   for (int i = 1; i <= q; ++i) {
  149.     scanf("%d %d", &u, &v);
  150.     switch (u) {
  151.       case 1:
  152.         toggleVPS(v);
  153.         break;
  154.       case 2:
  155.         printf("%lld\n", getSum(v));
  156.         break;
  157.     }
  158.   }
  159. }
  160. int main() {
  161.   program();
  162.   return 0;
  163. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 3
2 1
1 5
2 2
1 3
2 1
2 3
stdout
copy 
12
6
23
16
https://ideone.com/oeRNde
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!