fork download
copy 
  1. /**
  2.  * Solution for "Cay thong" (Pine Tree)
  3.  * Algorithm: Heavy-Light Decomposition + Segment Tree Beats + Fenwick Tree
  4.  * Complexity: O((N + Q) * log^2 N + V * log V * log Q)
  5.  */
  6.  
  7. #include <iostream>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <cstdio>
  11.  
  12. using namespace std;
  13.  
  14. // Maximum number of nodes and maximum value of A_i
  15. const int MAXN = 200005;
  16. const int MAXV = 200005;
  17.  
  18. int N, Q;
  19. int raw_A[MAXN]; // Input values (1-based index)
  20. vector<int> adj[MAXN];
  21.  
  22. // --- HLD Variables ---
  23. int parent_node[MAXN], depth[MAXN], heavy[MAXN], head[MAXN], pos[MAXN];
  24. int sz[MAXN];
  25. int cur_pos = 0;
  26. int A_hld[MAXN]; // Values reordered by HLD
  27.  
  28. // --- Global Statistics ---
  29. // BIT stores frequencies of values. Size covers 0 to MAXV.
  30. int bit[MAXV + 10]; 
  31. long long global_sum = 0; // Sum of all A_v
  32.  
  33. // Helper to update BIT (1-based indexing internally)
  34. void bit_update(int idx, int val) {
  35.     idx++; // Shift 0-based value to 1-based index
  36.     for (; idx < MAXV + 10; idx += idx & -idx)
  37.         bit[idx] += val;
  38. }
  39.  
  40. // Helper to query BIT prefix sum
  41. int bit_query(int idx) {
  42.     idx++; 
  43.     int sum = 0;
  44.     if (idx >= MAXV + 10) idx = MAXV + 9;
  45.     for (; idx > 0; idx -= idx & -idx)
  46.         sum += bit[idx];
  47.     return sum;
  48. }
  49.  
  50. // Helper to query BIT range sum
  51. int bit_query_range(int l, int r) {
  52.     if (l > r) return 0;
  53.     return bit_query(r) - bit_query(l - 1);
  54. }
  55.  
  56. // --- Segment Tree ---
  57. // tree_max stores the maximum value in the range to optimize modulo updates
  58. int tree_max[4 * MAXN];
  59.  
  60. void build(int node, int start, int end) {
  61.     if (start == end) {
  62.         tree_max[node] = A_hld[start];
  63.         // Initialize global stats
  64.         bit_update(A_hld[start], 1);
  65.         global_sum += A_hld[start];
  66.     } else {
  67.         int mid = (start + end) / 2;
  68.         build(2 * node, start, mid);
  69.         build(2 * node + 1, mid + 1, end);
  70.         tree_max[node] = max(tree_max[2 * node], tree_max[2 * node + 1]);
  71.     }
  72. }
  73.  
  74. // Segment Tree Beats update for Modulo
  75. void update_seg(int node, int start, int end, int l, int r, int w) {
  76.     // If range is outside or max value is less than w, no update needed
  77.     if (start > end || start > r || end < l || tree_max[node] < w)
  78.         return;
  79.  
  80.     // Leaf node: perform update
  81.     if (start == end) {
  82.         int old_val = tree_max[node];
  83.         int new_val = old_val % w;
  84.         tree_max[node] = new_val;
  85.  
  86.         // Update global frequency and sum
  87.         bit_update(old_val, -1);
  88.         bit_update(new_val, 1);
  89.         global_sum -= old_val;
  90.         global_sum += new_val;
  91.         return;
  92.     }
  93.  
  94.     int mid = (start + end) / 2;
  95.     update_seg(2 * node, start, mid, l, r, w);
  96.     update_seg(2 * node + 1, mid + 1, end, l, r, w);
  97.     tree_max[node] = max(tree_max[2 * node], tree_max[2 * node + 1]);
  98. }
  99.  
  100. // --- HLD Functions ---
  101. void dfs_sz(int u, int p) {
  102.     sz[u] = 1;
  103.     parent_node[u] = p;
  104.     depth[u] = depth[p] + 1;
  105.     heavy[u] = -1;
  106.     int max_sz = 0;
  107.     for (int v : adj[u]) {
  108.         if (v != p) {
  109.             dfs_sz(v, u);
  110.             sz[u] += sz[v];
  111.             if (sz[v] > max_sz) {
  112.                 max_sz = sz[v];
  113.                 heavy[u] = v;
  114.             }
  115.         }
  116.     }
  117. }
  118.  
  119. void dfs_hld(int u, int h) {
  120.     head[u] = h;
  121.     pos[u] = ++cur_pos;
  122.     A_hld[cur_pos] = raw_A[u]; // Map raw value to HLD position
  123.     if (heavy[u] != -1)
  124.         dfs_hld(heavy[u], h);
  125.     for (int v : adj[u]) {
  126.         if (v != parent_node[u] && v != heavy[u])
  127.             dfs_hld(v, v);
  128.     }
  129. }
  130.  
  131. void path_update(int u, int v, int w) {
  132.     while (head[u] != head[v]) {
  133.         if (depth[head[u]] > depth[head[v]]) swap(u, v);
  134.         update_seg(1, 1, N, pos[head[v]], pos[v], w);
  135.         v = parent_node[head[v]];
  136.     }
  137.     if (depth[u] > depth[v]) swap(u, v);
  138.     update_seg(1, 1, N, pos[u], pos[v], w);
  139. }
  140.  
  141. int main() {
  142.     // Fast I/O
  143.     ios_base::sync_with_stdio(false);
  144.     cin.tie(NULL);
  145.  
  146.     if (!(cin >> N >> Q)) return 0;
  147.  
  148.     for (int i = 1; i <= N; i++) cin >> raw_A[i];
  149.  
  150.     for (int i = 0; i < N - 1; i++) {
  151.         int u, v;
  152.         cin >> u >> v;
  153.         adj[u].push_back(v);
  154.         adj[v].push_back(u);
  155.     }
  156.  
  157.     // Preprocessing
  158.     dfs_sz(1, 0);
  159.     dfs_hld(1, 1);
  160.     build(1, 1, N);
  161.  
  162.     // Process Queries
  163.     for (int t = 1; t <= Q; t++) {
  164.         int x, y, w;
  165.         cin >> x >> y >> w;
  166.  
  167.         // 1. Update path
  168.         path_update(x, y, w);
  169.  
  170.         // 2. Calculate beauty
  171.         // Formula: Sum(val % t) = Sum(val) - t * Sum(floor(val/t))
  172.         long long current_beauty = global_sum;
  173.  
  174.         // Iterate k such that floor(val/t) = k
  175.         // Range of val: [k*t, (k+1)*t - 1]
  176.         for (int k = 1; k * t <= MAXV; k++) { 
  177.              int l = k * t;
  178.              int r = min((k + 1) * t - 1, MAXV);
  179.              int count = bit_query_range(l, r);
  180.              current_beauty -= (long long)k * t * count;
  181.         }
  182.         cout << current_beauty << "\n";
  183.     }
  184.  
  185.     return 0;
  186. }
Success #stdin #stdout 0.01s 13952KB
comments (?)
stdin
copy 
5
2 1 4 4 8
1 2
2 3
3 4
4 5
1 5 5
1 5 3
3 3 1
stdout
copy 
0
1
https://ideone.com/CITsqF
language:
C++14 (gcc 8.3)
created:
8 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!