fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e5)+7;
  14. const int LOG = 20;
  15.  
  16. int n , q , a[maxN] , lg2[maxN] , val[maxN][LOG + 1];
  17. vector<int> g[maxN];
  18.  
  19. int h[maxN] , p[maxN] , sz[maxN];
  20.  
  21. void dfs(int u){
  22.     sz[u] = 1;
  23.     for (int v : g[u]){
  24.         if (v != p[u]){
  25.             p[v] = u;
  26.             h[v] = h[u] + 1;
  27.             dfs(v);
  28.             sz[u] += sz[v];
  29.         }
  30.     }
  31. }
  32.  
  33. int head[maxN] , chain[maxN] , pos[maxN] , numChain = 1 , numPos = 0;
  34. int lef[maxN] , rig[maxN] , pre[maxN] , nxt[maxN];
  35.  
  36. void hld(int u){
  37.     if (head[numChain] == 0) head[numChain] = u;
  38.     chain[u] = numChain;
  39.     pos[u] = ++numPos;
  40.     int heavy = -1;
  41.     for (int v : g[u]){
  42.         if (v != p[u] && (heavy == -1 || sz[heavy] < sz[v])){
  43.             heavy = v;
  44.         }
  45.     }
  46.     if (heavy != -1) hld(heavy);
  47.     for (int v : g[u]){
  48.         if (v != p[u] && v != heavy){
  49.             numChain++;
  50.             hld(v);
  51.         }
  52.     }
  53. }
  54.  
  55. int lca(int u , int v){
  56.     while (chain[u] != chain[v]){
  57.         if (h[head[chain[u]]] > h[head[chain[v]]]) swap(u , v);
  58.         v = p[head[chain[v]]];
  59.     }
  60.     if (h[u] > h[v]) swap(u , v);
  61.     return u;
  62. }
  63.  
  64. int getMin(int l , int r){
  65.     int k = lg2[r - l + 1];
  66.     return min(val[l][k] , val[r - (1<<k) + 1][k]);
  67. }
  68.  
  69. vector<ii> range;
  70.  
  71. void get_range(int u , int root , int t){
  72.     range.clear();
  73.     while (chain[u] != chain[root]){
  74.         range.push_back({pos[head[chain[u]]] , pos[u]});
  75.         u = p[head[chain[u]]];
  76.     }
  77.     range.push_back({pos[root] + t , pos[u]});
  78. }
  79.  
  80. void solve(){
  81.     cin >> n >> q;
  82.     for (int i = 1 ; i < n ; i++){
  83.         int u , v;
  84.         cin >> u >> v;
  85.         g[u].push_back(v);
  86.         g[v].push_back(u);
  87.     }
  88.     for (int i = 1 ; i <= n ; i++) cin >> a[i];
  89.     dfs(1);
  90.     hld(1);
  91.     for (int i = 1 ; i <= numChain ; i++){
  92.         lef[i] = INT_MAX;
  93.         rig[i] = INT_MIN;
  94.     }
  95.     for (int i = 1 ; i <= n ; i++){
  96.         lef[chain[i]] = min(lef[chain[i]] , pos[i]);
  97.         rig[chain[i]] = max(rig[chain[i]] , pos[i]);
  98.     }
  99.     for (int i = 1 ; i <= n ; i++){
  100.         val[pos[i]][0] = a[i];
  101.         lg2[i] = __lg(i);
  102.     }
  103.     for (int j = 1 ; j <= LOG ; j++){
  104.         for (int i = 1 ; i + (1<<j) - 1 <= n ; i++){
  105.             val[i][j] = min(val[i][j - 1] , val[i + (1<<(j - 1))][j - 1]);
  106.         }
  107.     }
  108.     while (q--){
  109.         int u , v , x;
  110.         cin >> u >> v >> x;
  111.         int root = lca(u , v);
  112.         get_range(u , root , 1);
  113.         for (auto it : range){
  114.             int curL = it.fi;
  115.             int curR = it.se;
  116.             while (curL <= curR){
  117.                 int L = curL , R = curR , nxtR = -1;
  118.                 while (L <= R){
  119.                     int M = (L + R) / 2;
  120.                     if (getMin(M , curR) <= x){
  121.                         nxtR = M;
  122.                         L = M + 1;
  123.                     }
  124.                     else{
  125.                         R = M - 1;
  126.                     }
  127.                 }
  128.                 if (nxtR == -1) break;
  129.                 x %= val[nxtR][0];
  130.                 curR = nxtR - 1;
  131.             }
  132.         }
  133.         //--------------------------------------------------
  134.         get_range(v , root , 0);
  135.         reverse(all(range));
  136.         for (auto it : range){
  137.             int curL = it.fi;
  138.             int curR = it.se;
  139.             while (curL <= curR){
  140.                 int L = curL , R = curR , nxtL = -1;
  141.                 while (L <= R){
  142.                     int M = (L + R) / 2;
  143.                     if (getMin(curL , M) <= x){
  144.                         nxtL = M;
  145.                         R = M - 1;
  146.                     }
  147.                     else{
  148.                         L = M + 1;
  149.                     }
  150.                 }
  151.                 if (nxtL == -1) break;
  152.                 x %= val[nxtL][0];
  153.                 curL = nxtL + 1;
  154.             }
  155.         }
  156.         cout << x << "\n";
  157.     }
  158. }
  159.  
  160. #define name "J"
  161.  
  162. int main(){
  163.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  164.     if (fopen(name".INP" , "r")){
  165.         freopen(name".INP" , "r" , stdin);
  166.         freopen(name".OUT" , "w" , stdout);
  167.     }
  168.     int t = 1; //cin >> t;
  169.     while (t--) solve();
  170.     return 0;
  171. }
Success #stdin #stdout 0.01s 13912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/esnYsu
language:
C++ (gcc 8.3)
created:
3 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!