fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. // Khuyên dùng avx2 thay vì avx512 vì nhiều judge (Codeforces, VNOI) không hỗ trợ tập lệnh avx512, dễ gây RE/WA.
  3. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. // ===================== ROBUST FAST IO =====================
  9. namespace FastIO {
  10.     const int BUF_SIZE = 1 << 16;
  11.     char buf[BUF_SIZE];
  12.     int buf_pos = BUF_SIZE, buf_len = BUF_SIZE;
  13.  
  14.     inline char read_char() {
  15.         if (buf_pos == buf_len) {
  16.             buf_pos = 0;
  17.             buf_len = fread(buf, 1, BUF_SIZE, stdin);
  18.             if (buf_pos == buf_len) return EOF;
  19.         }
  20.         return buf[buf_pos++];
  21.     }
  22.  
  23.     inline bool read_int(int &x) {
  24.         char c = read_char();
  25.         while (c != EOF && c <= 32) c = read_char();
  26.         if (c == EOF) return false;
  27.         int sig = 1;
  28.         if (c == '-') { sig = -1; c = read_char(); }
  29.         x = 0;
  30.         while (c > 32) { x = x * 10 + (c - '0'); c = read_char(); }
  31.         x *= sig;
  32.         return true;
  33.     }
  34.  
  35.     inline bool read_ll(long long &x) {
  36.         char c = read_char();
  37.         while (c != EOF && c <= 32) c = read_char();
  38.         if (c == EOF) return false;
  39.         int sig = 1;
  40.         if (c == '-') { sig = -1; c = read_char(); }
  41.         x = 0;
  42.         while (c > 32) { x = x * 10 + (c - '0'); c = read_char(); }
  43.         x *= sig;
  44.         return true;
  45.     }
  46.  
  47.     char out_buf[BUF_SIZE];
  48.     int out_pos = 0;
  49.  
  50.     inline void write_char(char c) {
  51.         if (out_pos == BUF_SIZE) {
  52.             fwrite(out_buf, 1, out_pos, stdout);
  53.             out_pos = 0;
  54.         }
  55.         out_buf[out_pos++] = c;
  56.     }
  57.  
  58.     inline void write_ll(long long x) {
  59.         if (x == 0) { write_char('0'); return; }
  60.         unsigned long long ux = x; 
  61.         if (x < 0) { write_char('-'); ux = -x; }
  62.         char s[24]; int idx = 0;
  63.         while (ux > 0) { s[idx++] = (ux % 10) + '0'; ux /= 10; }
  64.         while (idx > 0) write_char(s[--idx]);
  65.     }
  66.  
  67.     inline void flush() {
  68.         if (out_pos > 0) {
  69.             fwrite(out_buf, 1, out_pos, stdout);
  70.             out_pos = 0;
  71.         }
  72.     }
  73. }
  74.  
  75. // ===================== SQRT DECOMP RARS CHUẨN =====================
  76. // Tách biệt việc cộng sum_block ra khỏi vòng lặp để trình biên dịch có thể bung SIMD Parallel Packing
  77. struct SqrtRARS {
  78.     static const int BLOCK = 256;
  79.     alignas(64) long long p[100005];
  80.     alignas(64) long long lazy[100005 / BLOCK + 5];
  81.     alignas(64) long long sum_block[100005 / BLOCK + 5];
  82.  
  83.     inline void add(int l, int r, long long val) {
  84.         if (l > r) return;
  85.         int bl = l / BLOCK, br = r / BLOCK;
  86.         if (bl == br) {
  87.             sum_block[bl] += val * (r - l + 1);
  88.             #pragma GCC ivdep
  89.             for (int i = l; i <= r; ++i) p[i] += val;
  90.         } else {
  91.             sum_block[bl] += val * ((bl + 1) * BLOCK - l);
  92.             #pragma GCC ivdep
  93.             for (int i = l; i < (bl + 1) * BLOCK; ++i) p[i] += val;
  94.  
  95.             for (int b = bl + 1; b < br; ++b) {
  96.                 lazy[b] += val;
  97.                 sum_block[b] += val * BLOCK;
  98.             }
  99.  
  100.             sum_block[br] += val * (r - br * BLOCK + 1);
  101.             #pragma GCC ivdep
  102.             for (int i = br * BLOCK; i <= r; ++i) p[i] += val;
  103.         }
  104.     }
  105.  
  106.     inline long long query(int l, int r) {
  107.         if (l > r) return 0;
  108.         long long res = 0;
  109.         int bl = l / BLOCK, br = r / BLOCK;
  110.         if (bl == br) {
  111.             res += lazy[bl] * (r - l + 1);
  112.             long long temp = 0;
  113.             #pragma GCC ivdep
  114.             for (int i = l; i <= r; ++i) temp += p[i];
  115.             res += temp;
  116.         } else {
  117.             res += lazy[bl] * ((bl + 1) * BLOCK - l);
  118.             long long temp_l = 0;
  119.             #pragma GCC ivdep
  120.             for (int i = l; i < (bl + 1) * BLOCK; ++i) temp_l += p[i];
  121.             res += temp_l;
  122.  
  123.             for (int b = bl + 1; b < br; ++b) res += sum_block[b];
  124.  
  125.             res += lazy[br] * (r - br * BLOCK + 1);
  126.             long long temp_r = 0;
  127.             #pragma GCC ivdep
  128.             for (int i = br * BLOCK; i <= r; ++i) temp_r += p[i];
  129.             res += temp_r;
  130.         }
  131.         return res;
  132.     }
  133. };
  134.  
  135. // ===================== MAIN OFFLINE TREE LOGIC =====================
  136. const int MOD = 1e9 + 7;
  137. const int B = 700; // Giữ nguyên B=700 cho thuật toán block query trên cây, không giảm xuống 256.
  138.  
  139. struct Edge { int v, id; };
  140. struct QueryInfo { int u, c, id; };
  141. struct Event { int type; int u; int c; long long v; int id; };
  142.  
  143. int N, Q;
  144.  
  145. alignas(64) int global_C[100005];
  146. alignas(64) long long global_V[100005];
  147. alignas(64) long long global_W[100005];
  148. alignas(64) int edge_u[100005], edge_v[100005];
  149.  
  150. vector<Edge> spatial_adj[100005];
  151.  
  152. alignas(64) int v_type[100005];
  153. alignas(64) int v_u[100005], v_c[100005]; 
  154. alignas(64) long long v_v[100005];
  155. alignas(64) int v_edge[100005]; 
  156. alignas(64) long long v_w[100005];
  157. vector<int> v_adj[100005];
  158. vector<QueryInfo> q_list[100005];
  159.  
  160. alignas(64) int old_c[100005]; 
  161. alignas(64) long long old_v[100005];
  162. alignas(64) long long old_w[100005];
  163.  
  164. vector<Event> E;
  165. alignas(64) long long query_answers[100005];
  166. int query_count = 0;
  167.  
  168. int tin[100005], tout[100005], timer = 0;
  169. int euler[200005], euler_depth[200005], first_occ[100005], euler_timer = 0;
  170. int st_lca[18][200005];
  171. int parent_orig[100005], edge_id_orig[100005];
  172.  
  173. void dfs_lca(int u, int p, int d) {
  174.     tin[u] = ++timer;
  175.     euler[++euler_timer] = u;
  176.     euler_depth[euler_timer] = d;
  177.     first_occ[u] = euler_timer;
  178.     parent_orig[u] = p;
  179.     for (auto& edge : spatial_adj[u]) {
  180.         int v = edge.v;
  181.         if (v != p) {
  182.             edge_id_orig[v] = edge.id;
  183.             dfs_lca(v, u, d + 1);
  184.             euler[++euler_timer] = u;
  185.             euler_depth[euler_timer] = d;
  186.         }
  187.     }
  188.     tout[u] = timer;
  189. }
  190.  
  191. void build_rmq() {
  192.     for (int i = 1; i <= euler_timer; ++i) st_lca[0][i] = i;
  193.     for (int j = 1; (1 << j) <= euler_timer; ++j) {
  194.         for (int i = 1; i + (1 << j) - 1 <= euler_timer; ++i) {
  195.             int a = st_lca[j-1][i];
  196.             int b = st_lca[j-1][i + (1 << (j-1))];
  197.             st_lca[j][i] = (euler_depth[a] < euler_depth[b]) ? a : b;
  198.         }
  199.     }
  200. }
  201.  
  202. int get_lca(int u, int v) {
  203.     int L = first_occ[u], R = first_occ[v];
  204.     if (L > R) swap(L, R);
  205.     int j = __lg(R - L + 1);
  206.     int a = st_lca[j][L];
  207.     int b = st_lca[j][R - (1 << j) + 1];
  208.     return euler[(euler_depth[a] < euler_depth[b]) ? a : b];
  209. }
  210.  
  211. void prep_dfs(int v) {
  212.     if (v != 0) {
  213.         if (v_type[v] == 1) {
  214.             old_c[v] = global_C[v_u[v]]; old_v[v] = global_V[v_u[v]];
  215.             global_C[v_u[v]] = v_c[v];   global_V[v_u[v]] = v_v[v];
  216.         } else {
  217.             old_w[v] = global_W[v_edge[v]];
  218.             global_W[v_edge[v]] = v_w[v];
  219.         }
  220.     }
  221.     for (int nxt : v_adj[v]) prep_dfs(nxt);
  222.     if (v != 0) {
  223.         if (v_type[v] == 1) {
  224.             global_C[v_u[v]] = old_c[v]; global_V[v_u[v]] = old_v[v];
  225.         } else {
  226.             global_W[v_edge[v]] = old_w[v];
  227.         }
  228.     }
  229. }
  230.  
  231. void build_E(int v) {
  232.     for (auto& q : q_list[v]) E.push_back({3, q.u, q.c, 0, q.id});
  233.     for (int nxt : v_adj[v]) {
  234.         if (v_type[nxt] == 1) E.push_back({1, v_u[nxt], v_c[nxt], v_v[nxt], 0});
  235.         else E.push_back({2, v_edge[nxt], 0, v_w[nxt], 0});
  236.  
  237.         build_E(nxt);
  238.  
  239.         if (v_type[nxt] == 1) E.push_back({1, v_u[nxt], old_c[nxt], old_v[nxt], 0});
  240.         else E.push_back({2, v_edge[nxt], 0, old_w[nxt], 0});
  241.     }
  242. }
  243.  
  244. alignas(64) int color_map[100005];
  245. bool in_VQ[100005];
  246. bool is_changing[100005];
  247. alignas(64) int vq_idx[100005];
  248. alignas(64) int vq_parent[100005];
  249. alignas(64) long long D_stat[100005];
  250. alignas(64) long long D_true[100005];
  251. alignas(64) int p_x[100005];
  252.  
  253. alignas(64) int C_curr[100005];
  254. alignas(64) long long V_curr[100005];
  255. alignas(64) long long W_curr[100005];
  256.  
  257. alignas(64) int SumV[15000][750];
  258. alignas(64) int SumVD[15000][750];
  259. vector<int> active_p[750];
  260.  
  261. void dfs_spatial(int u, int p, long long d, int anc) {
  262.     if (in_VQ[u]) anc = u;
  263.     p_x[u] = anc;
  264.     D_stat[u] = d;
  265.     for (auto& edge : spatial_adj[u]) {
  266.         int v = edge.v;
  267.         if (v != p) dfs_spatial(v, u, (d + global_W[edge.id]) % MOD, anc);
  268.     }
  269. }
  270.  
  271. int main() {
  272.     if (!FastIO::read_int(N) || !FastIO::read_int(Q)) return 0;
  273.  
  274.     for (int i = 1; i <= N; ++i) FastIO::read_int(global_C[i]);
  275.     for (int i = 1; i <= N; ++i) FastIO::read_ll(global_V[i]);
  276.     for (int i = 1; i < N; ++i) {
  277.         FastIO::read_int(edge_u[i]);
  278.         FastIO::read_int(edge_v[i]);
  279.         FastIO::read_ll(global_W[i]);
  280.         spatial_adj[edge_u[i]].push_back({edge_v[i], i});
  281.         spatial_adj[edge_v[i]].push_back({edge_u[i], i});
  282.     }
  283.  
  284.     dfs_lca(1, 0, 0);
  285.     build_rmq();
  286.  
  287.     int version_nodes = 0;
  288.     int current_version = 0;
  289.     vector<int> version_at_query(Q + 1, 0);
  290.  
  291.     for (int i = 1; i <= Q; ++i) {
  292.         int type; FastIO::read_int(type);
  293.         if (type == 1) {
  294.             int u, c; long long v; 
  295.             FastIO::read_int(u); FastIO::read_int(c); FastIO::read_ll(v);
  296.             v_adj[current_version].push_back(++version_nodes);
  297.             v_type[version_nodes] = 1;
  298.             v_u[version_nodes] = u; v_c[version_nodes] = c; v_v[version_nodes] = v;
  299.             current_version = version_nodes;
  300.         } else if (type == 2) {
  301.             int edge_id; long long w; 
  302.             FastIO::read_int(edge_id); FastIO::read_ll(w);
  303.             v_adj[current_version].push_back(++version_nodes);
  304.             v_type[version_nodes] = 2;
  305.             v_edge[version_nodes] = edge_id; v_w[version_nodes] = w;
  306.             current_version = version_nodes;
  307.         } else if (type == 3) {
  308.             int u, c; 
  309.             FastIO::read_int(u); FastIO::read_int(c);
  310.             q_list[current_version].push_back({u, c, ++query_count});
  311.         } else if (type == 4) {
  312.             int k; FastIO::read_int(k);
  313.             current_version = version_at_query[k];
  314.         }
  315.         version_at_query[i] = current_version;
  316.     }
  317.  
  318.     prep_dfs(0);
  319.     build_E(0);
  320.  
  321.     memset(color_map, -1, sizeof(color_map));
  322.     int M = E.size();
  323.  
  324.     for (int L = 0; L < M; L += B) {
  325.         int R = min(M - 1, L + B - 1);
  326.         vector<int> I = {1};
  327.         vector<int> E_change;
  328.  
  329.         for (int i = L; i <= R; ++i) {
  330.             if (E[i].type == 1 || E[i].type == 3) I.push_back(E[i].u);
  331.             else if (E[i].type == 2) {
  332.                 I.push_back(edge_u[E[i].u]);
  333.                 I.push_back(edge_v[E[i].u]);
  334.                 E_change.push_back(E[i].u);
  335.             }
  336.         }
  337.  
  338.         sort(I.begin(), I.end(), [](int a, int b) { return tin[a] < tin[b]; });
  339.         I.erase(unique(I.begin(), I.end()), I.end());
  340.  
  341.         int k_I = I.size();
  342.         for (int i = 0; i < k_I - 1; ++i) I.push_back(get_lca(I[i], I[i+1]));
  343.         sort(I.begin(), I.end(), [](int a, int b) { return tin[a] < tin[b]; });
  344.         I.erase(unique(I.begin(), I.end()), I.end());
  345.  
  346.         vector<int> st;
  347.         for (int i = 0; i < I.size(); ++i) {
  348.             int u = I[i];
  349.             vq_idx[u] = i;
  350.             in_VQ[u] = true;
  351.             while (!st.empty() && tout[st.back()] < tin[u]) st.pop_back();
  352.             vq_parent[u] = st.empty() ? 0 : st.back();
  353.             st.push_back(u);
  354.         }
  355.  
  356.         sort(E_change.begin(), E_change.end());
  357.         E_change.erase(unique(E_change.begin(), E_change.end()), E_change.end());
  358.         for (int e : E_change) is_changing[e] = true;
  359.  
  360.         dfs_spatial(1, 0, 0, 1);
  361.  
  362.         vector<int> Q_C;
  363.         for (int i = L; i <= R; ++i) {
  364.             if (E[i].type == 3) {
  365.                 if (color_map[E[i].c] == -1) {
  366.                     color_map[E[i].c] = Q_C.size();
  367.                     Q_C.push_back(E[i].c);
  368.                 }
  369.             }
  370.         }
  371.  
  372.         int num_c = Q_C.size();
  373.         for (int i = 0; i < I.size(); ++i) {
  374.             for (int j = 0; j < num_c; ++j) SumV[i][j] = SumVD[i][j] = 0;
  375.         }
  376.         for (int j = 0; j < num_c; ++j) active_p[j].clear();
  377.  
  378.         for (int u = 1; u <= N; ++u) {
  379.             if (!in_VQ[u]) {
  380.                 int c_map = color_map[global_C[u]];
  381.                 if (c_map != -1) {
  382.                     int p = p_x[u];
  383.                     int p_idx = vq_idx[p];
  384.                     SumV[p_idx][c_map] = (SumV[p_idx][c_map] + global_V[u]) % MOD;
  385.                     long long d_px = (D_stat[u] - D_stat[p] + MOD) % MOD;
  386.                     // FIX: Modulo global_V trước khi nhân để tránh tràn giới hạn long long
  387.                     SumVD[p_idx][c_map] = (SumVD[p_idx][c_map] + (global_V[u] % MOD) * d_px) % MOD;
  388.                 }
  389.             }
  390.         }
  391.  
  392.         for (int i = 0; i < I.size(); ++i) {
  393.             for (int j = 0; j < num_c; ++j) {
  394.                 if (SumV[i][j] > 0 || SumVD[i][j] > 0) active_p[j].push_back(I[i]);
  395.             }
  396.         }
  397.  
  398.         for (int u : I) { C_curr[u] = global_C[u]; V_curr[u] = global_V[u]; }
  399.         for (int e : E_change) W_curr[e] = global_W[e];
  400.  
  401.         for (int i = L; i <= R; ++i) {
  402.             if (E[i].type == 1) {
  403.                 C_curr[E[i].u] = E[i].c; V_curr[E[i].u] = E[i].v;
  404.             } else if (E[i].type == 2) {
  405.                 W_curr[E[i].u] = E[i].v;
  406.             } else if (E[i].type == 3) {
  407.                 for (int u : I) {
  408.                     if (vq_parent[u] == 0) D_true[u] = 0;
  409.                     else {
  410.                         int p = vq_parent[u];
  411.                         long long len = 0;
  412.                         if (parent_orig[u] == p && is_changing[edge_id_orig[u]]) {
  413.                             len = W_curr[edge_id_orig[u]];
  414.                         } else {
  415.                             len = (D_stat[u] - D_stat[p] + MOD) % MOD;
  416.                         }
  417.                         D_true[u] = (D_true[p] + len) % MOD;
  418.                     }
  419.                 }
  420.  
  421.                 long long ans = 0;
  422.                 int q_u = E[i].u; int q_c = E[i].c;
  423.  
  424.                 for (int x : I) {
  425.                     if (C_curr[x] == q_c) {
  426.                         int lca_ux = get_lca(q_u, x);
  427.                         long long dist = (D_true[q_u] + D_true[x] - 2 * D_true[lca_ux]) % MOD;
  428.                         if (dist < 0) dist += MOD;
  429.                         ans = (ans + (V_curr[x] % MOD) * dist) % MOD;
  430.                     }
  431.                 }
  432.  
  433.                 int c_map = color_map[q_c];
  434.                 if (c_map != -1) {
  435.                     for (int p : active_p[c_map]) {
  436.                         int lca_up = get_lca(q_u, p);
  437.                         long long dist = (D_true[q_u] + D_true[p] - 2 * D_true[lca_up]) % MOD;
  438.                         if (dist < 0) dist += MOD;
  439.                         int p_idx = vq_idx[p];
  440.                         ans = (ans + 1LL * SumV[p_idx][c_map] * dist + SumVD[p_idx][c_map]) % MOD;
  441.                     }
  442.                 }
  443.                 query_answers[E[i].id] = ans;
  444.             }
  445.         }
  446.  
  447.         for (int i = L; i <= R; ++i) {
  448.             if (E[i].type == 1) {
  449.                 global_C[E[i].u] = E[i].c; global_V[E[i].u] = E[i].v;
  450.             } else if (E[i].type == 2) {
  451.                 global_W[E[i].u] = E[i].v;
  452.             }
  453.         }
  454.         for (int u : I) in_VQ[u] = false;
  455.         for (int e : E_change) is_changing[e] = false;
  456.         for (int c : Q_C) color_map[c] = -1;
  457.     }
  458.  
  459.     for (int i = 1; i <= query_count; ++i) {
  460.         FastIO::write_ll(query_answers[i]);
  461.         FastIO::write_char('\n');
  462.     }
  463.  
  464.     FastIO::flush();
  465.     return 0;
  466. }
  467.  
Success #stdin #stdout 0.01s 15880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uXdE23
language:
C++14 (clang 8.0)
created:
18 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!