fork download 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. #define piii pair<pii, int>
  4. #define vi vector<int>
  5. #define vll vector<ll>
  6. #define vvi vector<vi>
  7. #define vpii vector<pii>
  8. #define vvpii vector<vpii>
  9. #define f first
  10. #define s second
  11. #define oo 1000000001
  12. #define eb emplace_back
  13. #define pb push_back
  14. #define mpr make_pair
  15. #define size(v) (int)v.size()
  16. #define ln '\n'
  17. #define ull unsigned long long
  18. #define ll long long
  19. #define all(v) v.begin(), v.end()
  20.  
  21. using namespace std;
  22.  
  23. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  24.  
  25. struct edge {
  26.   int x, y, v, c, s;
  27.   int other(int node) {
  28.     return (x == node ? y : x);
  29.   }
  30. };
  31.  
  32. const int lg = 18;
  33. const int up = 1e5 + 5;
  34. vi g[up];
  35. int val[up], nval[up], cost[up];
  36. int parent[lg][up], stMin[lg][up];
  37. int level[up];
  38. edge e[up];
  39.  
  40. void dfs(int node, int par) {
  41.   level[node] = level[par] + 1;
  42.   parent[0][node] = par;
  43.   stMin[0][node] = nval[node];
  44.   for (int i = 1; i < lg; ++i) {
  45.     parent[i][node] = parent[i - 1][parent[i - 1][node]];
  46.     stMin[i][node] = min(stMin[i - 1][node], stMin[i - 1][parent[i - 1][node]]);
  47.   }
  48.   for (int i : g[node]) {
  49.     int to = e[i].other(node);
  50.     if (to != par) {
  51.       val[to] = e[i].v;
  52.       nval[to] = e[i].s;
  53.       cost[to] = e[i].c;
  54.       dfs(to, node);
  55.     }
  56.   }
  57. }
  58.  
  59. int lca(int x, int y) {
  60.   if (level[x] < level[y]) {
  61.     swap(x, y);
  62.   }
  63.   for (int i = lg - 1; i >= 0; --i) {
  64.     if (level[x] - (1 << i) >= level[y]) {
  65.       x = parent[i][x];
  66.     }
  67.   }
  68.   if (x == y) return x;
  69.   for (int i = lg - 1; i >= 0; --i) {
  70.     if (parent[i][x] != parent[i][y]) {
  71.       x = parent[i][x];
  72.       y = parent[i][y];
  73.     }
  74.   }
  75.   return parent[0][x];
  76. }
  77.  
  78. int getMin(int x, int y) {
  79.   if (level[x] < level[y]) {
  80.     swap(x, y);
  81.   }
  82.   int res = oo;
  83.   for (int i = lg - 1; i >= 0; --i) {
  84.     if (level[x] - (1 << i) >= level[y]) {
  85.       res = min(res, stMin[i][x]);
  86.       x = parent[i][x];
  87.     }
  88.   }
  89.   if (x != y) {
  90.     for (int i = lg - 1; i >= 0; --i) {
  91.       if (parent[i][x] != parent[i][y]) {
  92.         res = min(res, stMin[i][x]);
  93.         res = min(res, stMin[i][y]);
  94.         x = parent[i][x];
  95.         y = parent[i][y];
  96.       }
  97.     }
  98.     res = min(res, stMin[0][x]);
  99.     res = min(res, stMin[0][y]);
  100.   }
  101.   return res;
  102. }
  103.  
  104. const int MAX = 3e6 + 6;
  105. int nxt = 1;
  106. int root[MAX], L[MAX], R[MAX];
  107. ll tree[MAX];
  108.  
  109. pii pr[up];
  110. int pos[up];
  111.  
  112. void build(int v, int l, int r) {
  113.   if (l != r) {
  114.     int mid = (l + r) >> 1;
  115.     L[v] = ++nxt;
  116.     R[v] = ++nxt;
  117.     build(L[v], l, mid);
  118.     build(R[v], mid + 1, r);
  119.   }
  120. }
  121.  
  122. int update(int v, int l, int r, int _pos, int _cost) {
  123.   int idx = ++nxt;
  124.   if (l == r) {
  125.     tree[idx] = tree[v] + _cost;
  126.     return idx;
  127.   }
  128.   int mid = (l + r) >> 1;
  129.   L[idx] = L[v];
  130.   R[idx] = R[v];
  131.   if (_pos <= mid) {
  132.     L[idx] = update(L[idx], l, mid, _pos, _cost);
  133.   } else {
  134.     R[idx] = update(R[idx], mid + 1, r, _pos, _cost);
  135.   }
  136.   tree[idx] = tree[L[idx]] + tree[R[idx]];
  137.   return idx;
  138. }
  139.  
  140. void dfs2(int node, int par, int n) {
  141.   root[node] = update(root[par], 1, n, pos[node], cost[node]);
  142.   for (int i : g[node]) {
  143.     int to = e[i].other(node);
  144.     if (to != par) {
  145.       dfs2(to, node, n);
  146.     }
  147.   }
  148. }
  149.  
  150. int query(int _a, int _b, int _lca, int l, int r, ll e) {
  151.   if (l == r) {
  152.     return l;
  153.   }
  154.   int mid = (l + r) >> 1;
  155.   ll _cost = tree[L[_a]] + tree[L[_b]] - tree[L[_lca]] * 2;
  156.   if (_cost > e) {
  157.     return query(L[_a], L[_b], L[_lca], l, mid, e);
  158.   } else {
  159.     return query(R[_a], R[_b], R[_lca], mid + 1, r, e - _cost);
  160.   }
  161. }
  162. void solve() {
  163.   int n;
  164.   cin >> n;
  165.   for (int i = 1; i < n; ++i) {
  166.     cin >> e[i].x >> e[i].y >> e[i].v >> e[i].c >> e[i].s;
  167.     g[e[i].x].eb(i);
  168.     g[e[i].y].eb(i);
  169.   }
  170.   val[1] = nval[1] = oo;
  171.   cost[1] = 0;
  172.   dfs(1, 1);
  173.  
  174.   for (int i = 1; i <= n; ++i) {
  175.     pr[i].f = val[i];
  176.     pr[i].s = i;
  177.   }
  178.   sort(pr + 1, pr + n + 1);
  179.   for (int i = 1; i <= n; ++i) {
  180.     pos[pr[i].s] = i;
  181.   }
  182.   build(1, 1, n);
  183.   root[0] = 1;
  184.   dfs2(1, 0, n);
  185.   int q;
  186.   cin >> q;
  187.   for (int i = 0; i < q; ++i) {
  188.     int _a, _b;
  189.     ll _e;
  190.     cin >> _a >> _b >> _e;
  191.     int _lca = lca(_a, _b);
  192.     int _pos = query(root[_a], root[_b], root[_lca], 1, n, _e);
  193.     int res = min(pr[_pos].f, getMin(_a, _b));
  194.     cout << res << ln;
  195.   }
  196. }
  197. int main() {
  198.   ios_base::sync_with_stdio(false);
  199.   solve();
  200.   return 0;
  201. }
Runtime error #stdin #stdout 0.07s 14812KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/bZJLC6
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!