#include <bits/stdc++.h> using namespace std; #define file "bai4" //#define int long long #define ll long long #define pii pair<int, int> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define mask(i) (1 << i) const int N = 1e5, inf = 1e9, K = __lg(N); void MAX(int &a, int b) { a = max(a, b); } void MIN(int &a, int b) { a = min(a, b); } int n, m, q, curchain, Time; int h[N + 2], up[N + 2][K + 2], lg[N + 2], ans[N + 2], cnt[N + 2], in[N + 2], ID[N + 2], head[N + 2], sz[N + 2], par[N + 2], s[N + 2], t[N + 2], L[N + 2], R[N + 2]; bool ok[N + 2]; ll dp[N + 2], all[N + 2], fw[N + 2], X[N + 2], Y[N + 2], sum[N + 2], remain[N + 2]; vector<int> g[N + 2], val[N + 2]; vector<pii> ed, smt[N + 2]; void dfs(int u, int p) { h[u] = h[p] + 1; sz[u] = 1; for (int v : g[u]) if (v != p) { up[v][0] = u; for (int j = 1; j <= K; j++) { if (up[v][j - 1] == 0) break; up[v][j] = up[up[v][j - 1]][j - 1]; } dfs(v, u); sz[u] += sz[v]; } } void hld(int u, int p) { if (head[curchain] == 0) head[curchain] = u; ID[u] = curchain; in[u] = ++Time; par[u] = p; int big = 0; for (int v : g[u]) if (v != p && sz[v] > sz[big]) big = v; if (big > 0) hld(big, u); for (int v : g[u]) if (v != p && v != big) { curchain++; hld(v, u); } } void dfs2(int u, int p) { for (int v : g[u]) if (v != p) dp[v] += dp[u], dfs2(v, u); } int upk(int u, int k) { for (int j = 0; mask(j) <= k; j++) if (k & mask(j)) u = up[u][j]; return u; } void lca(int u, int v, int id) { if (h[u] < h[v]) swap(u, v); int U = u, V = v; int k = h[u] - h[v]; u = upk(u, k); if (u == v) { int w = u; u = U; v = V; if (v == w) swap(u, v); all[id] = dp[v] - dp[w]; u = upk(v, h[v] - h[w] - 1); smt[id].pb({v, u}); } else { k = lg[h[u]]; for (int j = k; j >= 0; j--) if (up[u][j] != up[v][j]) u = up[u][j], v = up[v][j]; smt[id].pb({U, u}); smt[id].pb({V, v}); u = up[u][0]; all[id] = dp[U] + dp[V] - 2 * dp[u]; } } void update(int u, int x) { while (u <= n) fw[u] += x, u += u & -u; } ll get(int u) { ll ans = 0; while (u > 0) ans += fw[u], u -= u & -u; return ans; } ll GET(int l, int r) { return get(r) - get(l - 1); } ll getpath(int u, int v) { ll res = 0; while (ID[u] > ID[v]) { res += GET(in[head[ID[u]]], in[u]); u = par[head[ID[u]]]; } res += GET(in[v], in[u]); return res; } ll getqry(int id) { ll res = 0; for (pii &x : smt[id]) res += getpath(x.fi, x.se); return res; } int lcaslow(int u, int v, int id) { ll sum = 0; vector<int> cur; if (h[u] < h[v]) swap(u, v); while (h[u] > h[v]) { for (int x : val[u]) cur.pb(x), sum += x; u = up[u][0]; } while (u != v) { for (int x : val[u]) cur.pb(x), sum += x; for (int x : val[v]) cur.pb(x), sum += x; u = up[u][0]; v = up[v][0]; } sort(cur.begin(), cur.end(), greater<int>()); if (sum <= Y[id]) return X[id]; for (int i = 0; i < sz(cur); i++) { if (i + 1 > X[id]) break; sum -= cur[i]; if (sum <= Y[id]) return X[id] - (i + 1); } return -1; } void Sub1(vector<pii> &f) { for (int i = 1; i <= m; i++) { int id, x; cin >> id >> x; id--; if (h[f[id].fi] > h[f[id].se]) val[f[id].fi].pb(x); else val[f[id].se].pb(x); } for (int i = 1; i <= q; i++) { cin >> s[i] >> t[i] >> X[i] >> Y[i]; cout << lcaslow(s[i], t[i], i) << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(file".inp", "r")) { freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } cin >> n >> m >> q; vector<pii> f; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; f.pb({u, v}); g[u].pb(v); g[v].pb(u); } for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; dfs(1, 0); // if (max({n, m, q}) <= 2e3) return Sub1(f), 0; hld(1, 0); for (int i = 1; i <= m; i++) { int id, x; cin >> id >> x; pii cur; cur.fi = x; id--; if (h[f[id].fi] > h[f[id].se]) cur.se = f[id].fi; else cur.se = f[id].se; dp[cur.se] += x; ed.pb(cur); } dfs2(1, 0); for (int i = 1; i <= q; i++) { cin >> s[i] >> t[i] >> X[i] >> Y[i]; L[i] = 1; R[i] = inf + 1; lca(s[i], t[i], i); } sort(ed.begin(), ed.end(), greater<pii>()); // for (pii &f : ed) cout << f.fi << " " << f.se << "\n"; bool run = 1; while (run) { run = 0; vector<pii> qry; for (int i = 1; i <= q; i++) if (L[i] <= R[i]) { qry.pb({(L[i] + R[i]) / 2, i}); run = 1; } sort(qry.begin(), qry.end(), greater<pii>()); for (int i = 1; i <= n; i++) fw[i] = 0; int pos = 0; for (pii &f : qry) { int id = f.se; while (pos < sz(ed) && ed[pos].fi >= f.fi) { update(in[ed[pos].se], ed[pos].fi); pos++; } ll cur = getqry(id); if (all[id] - cur <= Y[id]) { ok[id] = 1; sum[id] = cur; remain[id] = all[id] - cur; } else ok[id] = 0; } for (int i = 1; i <= q; i++) if (L[i] <= R[i]) { if (ok[i]) { ans[i] = (L[i] + R[i]) / 2; L[i] = (L[i] + R[i]) / 2 + 1; } else R[i] = (L[i] + R[i]) / 2 - 1; } } vector<pii> qry; for (int i = 1; i <= q; i++) qry.pb({ans[i], i}); sort(qry.begin(), qry.end(), greater<pii>()); for (int i = 1; i <= n; i++) fw[i] = 0; int pos = 0; for (pii &f : qry) { int id = f.se; while (pos < sz(ed) && ed[pos].fi >= f.fi) { update(in[ed[pos].se], 1); pos++; } ll cur = getqry(id); cnt[id] = cur; } for (int i = 1; i <= q; i++) { ll delta = (Y[i] - remain[i]) / ans[i]; if (delta >= cnt[i]) cout << X[i] << "\n"; else { cnt[i] -= delta; if (cnt[i] > X[i]) cout << -1 << "\n"; else cout << X[i] - cnt[i] << "\n"; } } }

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