fork download
copy 
  1. #include<bits/stdc++.h> //NeOWami
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define ft first
  6. #define sc second
  7. using pii = pair<int, int>;
  8. const int N = 2e5 + 5;
  9. int n, q, a[N];
  10. vector<int> G[N];
  11. struct query {
  12.     int x, y, w;
  13. } Q[N];
  14.  
  15. namespace sub1 {
  16. int par[N], h[N];
  17. void dfs(int u, int pre) {
  18.     for (int v: G[u]) if (v != pre) {
  19.         h[v] = h[u] + 1;
  20.         par[v] = u;
  21.         dfs(v, u);
  22.     }
  23. }
  24. void solve() {
  25.     par[1] = 1;
  26.     dfs(1, 1);
  27.     for (int t = 1; t <= q; t++) {
  28.         int x = Q[t].x, y = Q[t].y, w = Q[t].w;
  29.         while(x != y) {
  30.             if (h[x] < h[y]) swap(x, y);
  31.             a[x] %= w;
  32.             x = par[x];
  33.         }
  34.         a[x] %= w;
  35.         int ans = 0;
  36.         for (int i = 1; i <= n; i++) ans = ans + (a[i] % t);
  37.         cout << ans << "\n";
  38.     }
  39. }
  40. }///
  41.  
  42. bool checkLine() {
  43.     for (int u = 1; u < n; u++) {
  44.         bool flag = 0;
  45.         for (int v: G[u]) if (v == u + 1) flag = 1;
  46.         if (flag == 0) return 0;
  47.     }
  48.     return 1;
  49. }
  50.  
  51. namespace sub2 {
  52. bool checksub() {
  53.     if (!checkLine()) return 0;
  54.     for (int i = 1; i <= n; i++) if (a[i] > 2) return 0;
  55.     return 1;
  56. }
  57. int st[N * 4][3], on[N * 4][3];
  58. vector<int> lz[N * 4];
  59. void build(int id, int l, int r) {
  60.     if (l == r) {
  61.         st[id][a[l]]++;
  62.         lz[id].clear();
  63.         return;
  64.     }
  65.     int mid = l +r  >> 1;
  66.     build(id * 2, l, mid);
  67.     build(id * 2 + 1, mid + 1, r);
  68.     for (int i = 0; i <= 2; i++) {
  69.         st[id][i] = st[id * 2][i] + st[id * 2 + 1][i];
  70.     }
  71.     lz[id].clear();
  72. }
  73. void down(int id) {
  74.     if (lz[id].size()) {
  75.         for (int t: lz[id]) {
  76.             int cntNew[3] = {0, 0, 0};
  77.             if (!on[id * 2][t]) {
  78.                 for (int i = 0; i <= 2; i++) cntNew[i % t] += st[id * 2][i];
  79.                 for (int i = 0; i <= 2; i++) st[id * 2][i] = cntNew[i];
  80.                 lz[id * 2].push_back(t);
  81.                 on[id * 2][t] = 1;
  82.             }
  83.             cntNew[0] = cntNew[1] = cntNew[2] = 0;
  84.             if (!on[id * 2 + 1][t]) {
  85.                 for (int i = 0; i <= 2; i++) cntNew[i % t] += st[id * 2 + 1][i];
  86.                 for (int i = 0; i <= 2; i++) st[id * 2 + 1][i] = cntNew[i];
  87.                 lz[id * 2 + 1].push_back(t);
  88.                 on[id * 2 + 1][t] = 1;
  89.             }
  90.         }
  91.         lz[id].clear();
  92.     }
  93. }
  94. void update(int id, int l, int r, int u, int v, int t) {
  95.     if (l > v|| r < u) return;
  96.     if (l >= u && r <= v) {
  97.         if (!on[id][t]) {
  98.             int cntNew[3] = {0, 0, 0};
  99.             for (int i = 0; i <= 2; i++) cntNew[i % t] += st[id][i];
  100.             for (int i = 0; i <= 2; i++) st[id][i] = cntNew[i];
  101.             lz[id].push_back(t);
  102.             on[id][t] = 1;
  103.         }
  104.         return;
  105.     }
  106.     down(id);
  107.     int mid = l + r >> 1;
  108.     update(id * 2, l, mid, u, v, t);
  109.     update(id * 2 + 1, mid + 1, r, u, v, t);
  110.     for (int i = 0; i <= 2; i++) st[id][i] = st[id * 2][i] + st[id * 2 + 1][i];
  111. }
  112. void solve() {
  113.     build(1, 1, n);
  114.     for (int t = 1; t <= q; t++) {
  115.         int x = Q[t].x, y = Q[t].y, w = Q[t].w;
  116.         if (x > y) swap(x, y);
  117.         if (w <= 2) update(1, 1, n, x, y, w);
  118.         int ans = 0;
  119.         for (int i = 1; i <= 2; i++) ans = ans + (i % t) * st[1][i];
  120.         cout << ans << "\n";
  121.     }
  122. }
  123. }///
  124. int bit[N], bit2[N];
  125. inline void update(int id, int t, int bit[]) {
  126.     if (id == 0) return;
  127.     for (; id < N; id += id &- id) bit[id] += t;
  128. }
  129. inline int get(int id, int bit[]) {
  130.     int ans = 0;
  131.     for (; id > 0; id -= id &- id) ans = ans + bit[id];
  132.     return ans;
  133. }
  134. inline int getrange(int l, int r, int bit[]) {
  135.     return get(r, bit) - get(l - 1, bit);
  136. }
  137.  
  138. namespace sub3 {
  139. bool checksub() {
  140.     if (!checkLine()) return 0;
  141.     for (int i =1; i <= q; i++) if (Q[i].x != Q[i].y) return 0;
  142.     return 1;
  143. }
  144.  
  145. void solve() {
  146.     for (int i =1 ; i <= n; i++) {
  147.         update(a[i], 1, bit);
  148.         update(a[i], a[i], bit2);
  149.     }
  150.     for (int t = 1; t <= q; t++) {
  151.         int x = Q[t].x, y = Q[t].y, w = Q[t].w;
  152. //        cerr << t << ": " << x << " " << y << " " << w << "\n";
  153.         update(a[x], -1, bit);
  154.         update(a[x], -a[x], bit2);
  155.         a[x] %= w;
  156.         update(a[x], 1, bit);
  157.         update(a[x], a[x], bit2);
  158.         if (t == 1) {
  159.             cout << "0\n";
  160.             continue;
  161.         }
  162.         int ans = 0;
  163.         for (int l = 0; l < N; l += t) {
  164.             int r = min(N - 1, l + (t - 1));
  165. //            cerr << t << " " << l << " " << r << " -> " << "\n";
  166.             int all = getrange(l, r, bit2);
  167.             int del = l * getrange(l, r, bit);
  168.             ans = (ans + all - del);
  169. //            cerr << t << " " << l << " " << r << " -> " << all - del << "\n";
  170.         }
  171.         cout << ans << "\n";
  172.     }
  173. }
  174. }///
  175.  
  176.  
  177. namespace subcan {
  178. int par[N], h[N];
  179. void dfs(int u, int pre) {
  180.     for (int v: G[u]) if (v != pre) {
  181.         h[v] = h[u] + 1;
  182.         par[v] = u;
  183.         dfs(v, u);
  184.     }
  185. }
  186.  
  187. void solve() {
  188.     par[1] = 1;
  189.     dfs(1, 1);
  190.     for (int i =1 ; i <= n; i++) {
  191.         update(a[i], 1, bit);
  192.         update(a[i], a[i], bit2);
  193.     }
  194.     for (int t = 1; t <= q; t++) {
  195.         int x = Q[t].x, y = Q[t].y, w = Q[t].w;
  196. //        cerr << t << ": " << x << " " << y << " " << w << "\n";
  197.  
  198.  
  199.         while(x != y) {
  200.             if (h[x] < h[y]) swap(x, y);
  201.             if (a[x] >= w) {
  202.                 update(a[x], -1, bit);
  203.                 update(a[x], -a[x], bit2);
  204.                 a[x] %= w;
  205.                 update(a[x], 1, bit);
  206.                 update(a[x], a[x], bit2);
  207.             }
  208.             x = par[x];
  209.         }
  210.         if (a[x] >= w) {
  211.             update(a[x], -1, bit);
  212.             update(a[x], -a[x], bit2);
  213.             a[x] %= w;
  214.             update(a[x], 1, bit);
  215.             update(a[x], a[x], bit2);
  216.         }
  217.         if (t == 1) {
  218.             cout << "0\n";
  219.             continue;
  220.         }
  221.         int ans = 0;
  222.         for (int l = 0; l < N; l += t) {
  223.             int r = min(N - 1, l + (t - 1));
  224. //            cerr << t << " " << l << " " << r << " -> " << "\n";
  225.             int all = getrange(l, r, bit2);
  226.             int del = l * getrange(l, r, bit);
  227.             ans = (ans + all - del);
  228. //            cerr << t << " " << l << " " << r << " -> " << all - del << "\n";
  229.         }
  230.         cout << ans << "\n";
  231.     }
  232.  
  233. }
  234. }///
  235.  
  236. signed main() {
  237.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  238.     if (ifstream("PINE.inp")) {
  239.         freopen("PINE.inp", "r", stdin);
  240.         freopen("PINE.out", "w", stdout);
  241.     }
  242.     cin >> n >> q;
  243.     for (int i = 1; i <= n; i++) cin >> a[i];
  244.     for (int i =1 ; i < n; i++) {
  245.         int u, v; cin >> u >> v;
  246.         G[u].push_back(v);
  247.         G[v].push_back(u);
  248.     }
  249.     for (int i = 1; i <= q; i++) {
  250.         int x, y, w; cin >> x >> y >> w;
  251.         Q[i] = {x, y, w};
  252.     }
  253.     if (n <= 5000 && q <= 5000) return sub1::solve(), 0;
  254.     if (sub2::checksub()) return sub2::solve(), 0;
  255.     if (sub3::checksub()) return sub3::solve(), 0;
  256.     if (n * q <= 100000000) return sub1::solve(), 0;
  257.     return subcan::solve(), 0;
  258.     return 0;
  259. }
  260.  
Success #stdin #stdout 0.01s 34188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xplBeN
language:
C++14 (gcc 8.3)
created:
2 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!