fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 100005
  5. #define file
  6.  
  7. int n, m, q;
  8. vector<int> g[maxn];
  9.  
  10. struct edge {
  11.     int u, v;
  12. } edges[maxn];
  13.  
  14. struct station {
  15.     int id, cost;
  16. } stations[maxn];
  17.  
  18. vector<pair<int, int> > ups[maxn];
  19.  
  20. int par[20][maxn], deep[maxn];
  21. void pre_dfs (int u, int p) {
  22.     for (int v : g[u]) {
  23.         if (v == p) continue ;
  24.         deep[v] = deep[u] + 1;
  25.         par[0][v] = u;
  26.         for (int i = 1; i < 20; i++) par[i][v] = par[i - 1][par[i - 1][v]];
  27.  
  28.         pre_dfs (v, u);
  29.     }
  30. }
  31. int LCA (int u, int v) {
  32.     if (deep[u] < deep[v]) swap (u, v);
  33.     int dif = deep[u] - deep[v];
  34.  
  35.     for (int i = 19; i >= 0; i--) if ((dif >> i) & 1) {
  36.         u = par[i][u];
  37.     }
  38.  
  39.     if (u == v) return u;
  40.  
  41.     for (int i = 19; i >= 0; i--) if (par[i][u] != par[i][v]) {
  42.         u = par[i][u];
  43.         v = par[i][v];
  44.     }
  45.  
  46.     return par[0][u];
  47. }
  48.  
  49. int root[maxn], id_node;
  50. struct node {
  51.     ll val, cnt;
  52.     int le, ri;
  53. } tr[maxn * 20];
  54.  
  55. int update (int id, int l, int r, int pos, int val) {
  56.     int ne_id = ++id_node;
  57.     tr[ne_id] = tr[id];
  58.  
  59.     tr[ne_id].val += val;
  60.     tr[ne_id].cnt += 1;
  61.  
  62.     if (l == r) return ne_id;
  63.  
  64.     int mid = (l + r) >> 1;
  65.     if (pos <= mid) tr[ne_id].le = update (tr[id].le, l, mid, pos, val);
  66.     else tr[ne_id].ri = update (tr[id].ri, mid + 1, r, pos, val);
  67.  
  68.     return ne_id;
  69. }
  70.  
  71. int get_cnt (int u, int v, int lca, int l, int r, ll val) {
  72.     if (l == r) {
  73.         int cnt = tr[u].cnt + tr[v].cnt - 2 * tr[lca].cnt;
  74.         ll cur_val = tr[u].val + tr[v].val - 2ll * tr[lca].val;
  75.  
  76.         if (cur_val <= val) return cnt;
  77.         else return 0;
  78.     }
  79.  
  80.     int mid = (l + r) >> 1;
  81.     int cnt_le = tr[tr[u].le].cnt + tr[tr[v].le].cnt - 2 * tr[tr[lca].le].cnt;
  82.     ll val_le = tr[tr[u].le].val + tr[tr[v].le].val - 2ll * tr[tr[lca].le].val;
  83.  
  84.     if (val_le > val) return get_cnt (tr[u].le, tr[v].le, tr[lca].le, l, mid, val);
  85.     else return get_cnt (tr[u].ri, tr[v].ri, tr[lca].ri, mid + 1, r, val - val_le) + cnt_le;
  86. }
  87.  
  88. void dfs (int u, int p) {
  89.     root[u] = root[p];
  90.     for (auto x : ups[u]) {
  91.         root[u] = update (root[u], 1, m, x.first, x.second);
  92.     }
  93.  
  94.     for (int v : g[u]) {
  95.         if (v == p) continue ;
  96.         dfs (v, u);
  97.     }
  98. }
  99.  
  100. void read() {
  101.     cin >> n >> m >> q;
  102.     for (int i = 1; i < n; i++) {
  103.         int u, v;
  104.         cin >> u >> v;
  105.         edges[i] = {u, v};
  106.         g[u].push_back (v);
  107.         g[v].push_back (u);
  108.     }
  109.  
  110.     for (int i = 1; i <= m; i++) {
  111.         int id, cost;
  112.         cin >> id >> cost;
  113.         stations[i] = {id, cost};
  114.     }
  115. }
  116.  
  117. void solve() {
  118.     pre_dfs (1, -1);
  119.  
  120.     sort (stations + 1, stations + m + 1, [](const station& a, const station& b) {
  121.         return a.cost < b.cost;
  122.     });
  123.  
  124.     for (int i = 1; i <= m; i++) {
  125.         int id_e = stations[i].id, cost = stations[i].cost;
  126.  
  127.         int u = edges[id_e].u, v = edges[id_e].v;
  128.         if (par[0][u] == v) swap (u, v);
  129.  
  130.         ups[v].push_back ({i, cost});
  131.     }
  132.  
  133.     dfs (1, 0);
  134.  
  135.     while (q--) {
  136.         ll u, v, x, y;
  137.         cin >> u >> v >> x >> y;
  138.  
  139.         int lca = LCA (u, v);
  140.  
  141.         int tol_cnt = tr[root[u]].cnt + tr[root[v]].cnt - 2 * tr[root[lca]].cnt;
  142.         int cur_cnt = get_cnt (root[u], root[v], root[lca], 1, m, y);
  143.         int gold_needed = tol_cnt - cur_cnt;
  144.  
  145.         if (x < gold_needed) cout << "-1\n";
  146.         else cout << x - gold_needed << '\n';
  147.     }
  148. }
  149.  
  150. signed main() {
  151.     ios_base::sync_with_stdio(false);
  152.     cin.tie(0);cout.tie(0);
  153.  
  154.     if (fopen(file".INP","r")) {
  155.         freopen(file".INP","r",stdin);
  156.         freopen(file".OUT","w",stdout);
  157.     }
  158.  
  159.     read();
  160.     solve();
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 11452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Dgc6oq
language:
C++14 (gcc 8.3)
created:
1 day 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!