fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 2e5 + 5, mod = 1e9 + 7;
  17. int s[N] , hev[N] , d[N] , head[N] , pos[N] , cnt = 0 , par[N] , node[N];
  18. int st[4*N] , a[N] , bit[N] , sum = 0;
  19. int n , q; 
  20. vector <int> g[N];
  21.  
  22. void dfs(int u , int pa)
  23. {
  24.     s[u] = 1;
  25.     for (auto v : g[u])
  26.     if (v != pa)
  27.     {
  28.         d[v] = d[u] + 1;
  29.         par[v] = u;
  30.  
  31.         dfs(v , u);
  32.  
  33.         s[u] += s[v];
  34.         if (s[v] > s[hev[u]])
  35.             hev[u] = v;
  36.     }
  37. }
  38.  
  39. void hld(int u , int pa , int h)
  40. {
  41.     head[u] = h;
  42.     pos[u] = ++cnt;
  43.     node[cnt] = u;
  44.  
  45.     if (hev[u] != 0)
  46.         hld(hev[u] , u , h);
  47.  
  48.     for (auto v : g[u])
  49.     if (v != pa && v != hev[u])
  50.         hld(v , u , v);
  51. }
  52.  
  53. void upd_st(int i, int val, int id = 1, int l = 1, int r = n) 
  54. {
  55.     if (l > i || r < i)
  56.         return;
  57.  
  58.     if (l == r) 
  59.     {
  60.         st[id] = val;
  61.         return;
  62.     }
  63.  
  64.     int mid = (l + r) >> 1; 
  65.     upd_st(i, val, id * 2, l, mid);
  66.     upd_st(i, val, id * 2 + 1, mid + 1, r);
  67.     st[id] = max(st[2 * id] , st[2 * id + 1]);
  68. }
  69.  
  70. int get_st(int u, int v, int id = 1, int l = 1, int r = n)
  71. {
  72.     if (r < u || v < l) return 0;
  73.     if (u <= l && r <= v) return st[id];
  74.  
  75.     int mid = (l + r) >> 1;
  76.     return max(get_st(u, v, id * 2, l, mid) , get_st(u, v, id * 2 + 1, mid + 1, r));
  77. }
  78.  
  79. void upd_cnt(int x, int v) 
  80. {
  81.     x++;
  82. 	for (; x <= 200001; x += x & -x) bit[x] += v;
  83. }
  84. int get_cnt(int x) 
  85. {
  86.     x++;
  87. 	int res = 0;
  88. 	for (; x >= 1; x &= x - 1) res += bit[x];
  89. 	return res;
  90. }
  91.  
  92. void walk(int u, int v, int w, int id = 1, int l = 1, int r = n)
  93. {
  94.     if (st[id] < w || r < u || v < l) return;
  95.  
  96.     if (l == r)
  97.     {
  98.         int i = node[l]; //i la dinh cos pos[i] == l
  99.         upd_cnt(a[i] , -1);
  100.         sum -= a[i];
  101.  
  102.         a[i] %= w;
  103.         st[id] = a[i];
  104.  
  105.         sum += a[i];
  106.         upd_cnt(a[i] , 1);
  107.     }
  108.     else
  109.     {
  110.         int mid = (l + r) / 2;
  111.         walk(u, v, w, id * 2, l, mid);
  112.         walk(u, v, w, id * 2 + 1, mid + 1, r);
  113.  
  114.         st[id] = max(st[id * 2] , st[id * 2 + 1]);
  115.     }
  116. }
  117.  
  118. void lca(int u , int v , int w)
  119. {
  120.     while (head[u] != head[v])
  121.     {
  122.         if (d[head[u]] < d[head[v]])
  123.             swap(u , v);
  124.  
  125.         walk(pos[head[u]] , pos[u] , w);
  126.         u = par[head[u]];
  127.     }
  128.     if (d[u] < d[v])
  129.         swap(u , v);
  130.     walk(pos[v] , pos[u] , w);
  131. }
  132.  
  133. signed main()
  134. {
  135.     ios_base::sync_with_stdio(0);
  136.     cin.tie(0);  cout.tie(0);
  137.     //freopen(NAME".INP" , "r" , stdin);
  138.     //freopen(NAME".OUT" , "w" , stdout);
  139.  
  140.     cin >> n >> q;
  141.     fo(i, 1, n) cin >> a[i];
  142.     fo(i, 1, n - 1)
  143.     {
  144.         int u , v;
  145.         cin >> u >> v;
  146.         g[u].push_back(v);
  147.         g[v].push_back(u);
  148.     }
  149.  
  150.     d[1] = 1;
  151.     dfs(1 , 0);
  152.     hld(1 , 0 , 1);
  153.  
  154.     fo(i, 1, n)
  155.     {
  156.         upd_st(pos[i] , a[i]);
  157.         upd_cnt(a[i] , 1);
  158.         sum += a[i];
  159.     }
  160.  
  161.     fo(t, 1, q)
  162.     {
  163.         int x , y , w;
  164.         cin >> x >> y >> w;
  165.         lca(x , y , w);
  166.  
  167.         int res = sum , db = 0;
  168.         fo(k, 1, 200000 / t)
  169.         {
  170.             res -= (get_cnt(min((k + 1) * t - 1 , 200000LL)) - get_cnt(k * t - 1)) * k * t;
  171.         }
  172.         cout << res << '\n';
  173.     }
  174. }
  175. // haronnee_
Success #stdin #stdout 0.01s 15700KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sHed0s
language:
C++ (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!