#include<bits/stdc++.h> using namespace std; // define #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define ll long long #define ii pair <int , int> #define iii pair <int , ii> #define se second #define fi first #define all(v) (v).begin() , (v).end() #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin()) #define bit(x,i) (((x) >> (i)) & 1LL) #define flip(x,i) ((x) ^ (1LL << (i))) #define ms(d,x) memset(d , x , sizeof(d)) #define exist __exist #define ends __ends #define visit visited #define left __left #define right __right #define prev __prev #define next __next #define sitingfake 1 #define orz 1 //constant const long long mod = 1e9 + 7; const long long linf = 4557430888798830399LL; const long long nlinf = -4485090715960753727LL; const int LOG = 20; const int inf = 1061109567; const int ninf = -1044266559; const int dx[] = {0 , -1 , 0 , 1}; const int dy[] = {-1 , 0 , 1 , 0}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } void Plus(ll & a ,ll b) { b %= mod; a += b; if(a < 0) a += mod; a %= mod; return; } void Mul(ll & a, ll b) { (a *= (b % mod)) %= mod; return; } //code const int maxn = 1e5 + 7; int n , m , q; ii CheckPoint[maxn] , edges[maxn]; bool cmp(ii &a , ii & b) { return a.se < b.se; } struct Query { int u , v; ll Gold , Silver; int id; }Q[maxn]; int left[maxn] , right[maxn] , ans[maxn]; vector <int> Query[maxn]; // HLD int in[maxn] , out[maxn] , timer; int pos[maxn]; vector <int> adj[maxn]; int head[maxn] , heavy[maxn] , par[maxn] , depth[maxn]; int num[maxn]; int dfscount(int u , int p) { int cur = 1; int Max = 0; for(int v : adj[u]) { if(v != p) { par[v] = u; depth[v] = depth[u] + 1; int sz = dfscount(v , u); if(maximize(Max , sz)) { heavy[u] = v; } cur += sz; } } return cur; } void HLD(int u , int p , int h) { head[u] = h; in[u] = ++timer; if(heavy[u]) { HLD(heavy[u] , u , h); } for(int v : adj[u]) { if(v != p && v != heavy[u]) { HLD(v , u , v); } } } void dfs(int u , int p) { for(int v : adj[u]) { if(v != p) { num[v] += num[u]; dfs(v , u); } } } void init() { for(int i = 1; i < n; i++) { int u = edges[i].fi; int v = edges[i].se; if(in[u] <= in[v] && out[v] <= out[u]) { swap(u , v); swap(edges[i].fi , edges[i].se); } pos[i] = in[u]; } for(int i = 1; i <= m; i++) { num[edges[CheckPoint[i].fi].fi]++; } dfs(1 , -1); for(int i = 1; i <= q; i++) { left[i] = 1 , right[i] = m; } } // query pair <int , ll> bit[maxn]; void up(int x , int num , ll coins) { for(;x <= n; x += (x & -x)) { bit[x].fi += num; bit[x].se += coins; } } pair <int , ll> get(int x) { pair <int , ll> ans = {0 , 0}; for(;x > 0; x -= (x & -x)) { ans.fi += bit[x].fi; ans.se += bit[x].se; } return ans; } pair <int , ll> RangeQuery(int l , int r) { if(l > r) return {0 , 0}; pair <int ,ll> left = get(l - 1) , right = get(r); return {right.fi - left.fi , right.se - left.se}; } void reset() { for(int i = 1; i <= n; i++) { bit[i] = {0 , 0}; } } pair <int , ll> PathQuery(int u , int v) { pair <int , ll> ans = {0 , 0}; for(;head[v] != head[u]; v = par[head[v]]) { if(depth[head[u]] > depth[head[v]]) swap(u , v); pair <int , ll> tmp = RangeQuery(in[head[v]] , in[v]); ans.fi += tmp.fi; ans.se += tmp.se; } if(depth[u] > depth[v]) swap(u , v); pair <int , ll> tmp = RangeQuery(in[u] + 1 , in[v]); ans.fi += tmp.fi; ans.se += tmp.se; return ans; } int lca(int u , int v) { for(;head[u] != head[v]; v = par[head[v]]) { if(depth[head[u]] > depth[head[v]]) swap(u , v); } if(depth[u] > depth[v]) swap(u , v); return u; } void Process() { reset(); for(int d = 1; d <= m; d++) { up(pos[CheckPoint[d].fi] , 1 , CheckPoint[d].se); for(int i : Query[d]) { pair <int , ll> tmp = PathQuery(Q[i].u , Q[i].v); if(tmp.se <= Q[i].Silver) { ans[i] = tmp.fi; left[i] = d + 1; } else { right[i] = d - 1; } } Query[d].clear(); } } void solve(void) { cin >> n >> m >> q; for(int i = 1; i < n; i++) { int u , v; cin >> u >> v; edges[i] = {u , v}; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 1; i <= m; i++) { cin >> CheckPoint[i].fi >> CheckPoint[i].se; } for(int i = 1; i <= q; i++) { cin >> Q[i].u >> Q[i].v >> Q[i].Gold >> Q[i].Silver; } sort(CheckPoint + 1 , CheckPoint + m + 1 , cmp); dfscount(1 , -1); HLD(1 , -1 , 1); init(); while(1) { bool flag = 1; for(int i = 1; i <= q; i++) { if(left[i] <= right[i]) { flag = 0; Query[(left[i] + right[i]) >> 1].push_back(i); } } if(flag) break; Process(); } for(int i = 1; i <= q; i++) { int curPoint = num[Q[i].u] + num[Q[i].v] - 2 * num[lca(Q[i].u , Q[i].v)]; curPoint -= ans[i]; if(Q[i].Gold - curPoint < 0) { cout << -1 << "\n"; } else cout << Q[i].Gold - curPoint << "\n"; } } /** 5 4 1 1 2 1 3 2 4 2 5 2 9 2 4 3 5 4 7 3 4 2 11 **/ signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int tc = 1; // cin >> tc; while(tc--) solve(); // execute; }

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