#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define bigint __int128 #define emb emplace_back #define pb push_back #define pii pair <int, int> #define fi first #define se second #define all(v) v.begin(), v.end() #define Task "" #define MASK(k) (1ull << k) #define bitcnt(k) __builtin_popcount(k) #define testBit(n, k) ((n >> k) & 1) #define flipBit(n, k) (n ^ (1ll << k)) #define offBit(n, k) (n & ~MASK(k)) #define onBit(n, k) (n | (1ll << k)) template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;} template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;} const int N = 1e5 + 5, LG = 17, mod = 1e9 + 7; const ll INF = 1e18; struct FenwickTree { vector <ll> bit; FenwickTree (int len) { bit.assign(len + 1, 0); } void resize(int len) { bit.assign(len + 1, 0); } void update(int p, int val) { for (; p < bit.size(); p += p & -p) bit[p] += val; } ll get(int p) { ll res = 0; for (; p > 0; p -= p & -p) res += bit[p]; return res; } }; int n, m, q, par[N], h[N]; int st[N], en[N], up[N][LG], dfsTimes = 0; pii edge[N]; vector <int> adj[N]; struct Query { int u, v, x; ll y; pii range; int cntSilver, checkPoints; int lca; } query[N]; void dfs(int u, int p = -1) { st[u] = ++dfsTimes; for (int v: adj[u]) if (v != p) { par[v] = up[v][0] = u; h[v] = h[u] + 1; for (int i = 1; i < LG; i++) up[v][i] = up[up[v][i - 1]][i - 1]; dfs(v, u); } en[u] = ++dfsTimes; } int lca(int u, int v) { if (h[u] != h[v]) { if (h[u] < h[v]) swap(u, v); for (int i = 0, k = h[u] - h[v]; (1 << i) <= k; i++) if (testBit(k, i)) u = up[u][i]; } if (u == v) return u; for (int i = __lg(h[u]); i > -1; i--) if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; return up[u][0]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n >> m >> q; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); edge[i] = make_pair(u, v); } vector <pii> checkPoints; for (int i = 1; i <= m; i++) { int p, c; cin >> p >> c; checkPoints.emplace_back(c, p); } sort (all(checkPoints)); for (int i = 1; i <= q; i++) { cin >> query[i].u >> query[i].v >> query[i].x >> query[i].y; } dfs(1); for (int i = 1; i < n; i++) { if (par[edge[i].fi] == edge[i].se) swap(edge[i].fi, edge[i].se); // edge[i] = make_pair(p, u) } FenwickTree fenCnt(2 * n), fenSum(2 * n); for (auto [silver, e]: checkPoints) { auto [p, u] = edge[e]; fenCnt.update(st[u], 1); fenCnt.update(en[u], -1); } for (int i = 1; i <= q; i++) { int u = query[i].u, v = query[i].v; query[i].lca = lca(query[i].u, query[i].v); query[i].range = make_pair(-1, checkPoints.size() - 1); query[i].checkPoints = fenCnt.get(st[u]) + fenCnt.get(st[v]) - 2 * fenCnt.get(st[query[i].lca]); query[i].cntSilver = 0; } while (true) { vector <pii> events; for (int i = 1; i <= q; i++) if (query[i].range.fi != query[i].range.se) { int mid = (query[i].range.fi + query[i].range.se + 1) >> 1; events.emplace_back(mid, i); } if (events.empty()) break; sort (all(events)); int p = -1; fenSum.resize(2 * n), fenCnt.resize(2 * n); for (auto [k, id]: events) { while (p < k) { auto [silver, e] = checkPoints[++p]; auto [p, u] = edge[e]; fenSum.update(st[u], silver); fenSum.update(en[u], -silver); fenCnt.update(st[u], 1); fenCnt.update(en[u], -1); } int u = query[id].u, v = query[id].v; ll silverCoins = fenSum.get(st[u]) + fenSum.get(st[v]) - 2 * fenSum.get(st[query[id].lca]); if (silverCoins <= query[id].y) { query[id].range.fi = k; query[id].cntSilver = fenCnt.get(st[u]) + fenCnt.get(st[v]) - 2 * fenCnt.get(st[query[id].lca]); } else query[id].range.se = k - 1; } } for (int i = 1; i <= q; i++) { int useGold = query[i].checkPoints - query[i].cntSilver; int ans = query[i].x - useGold; if (ans < 0) ans = -1; cout << ans << '\n'; } }

currencies.cpp: In function 'int main()':
currencies.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:89:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~