#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll M = 1e5 + 10; ll base = 1<<18; ll maxlog = 17; ll nxt = 0; vector<ll> Tree(2*base,0); vector<vector<ll>> g(M), j(M, vector<ll>(maxlog+1)); vector<ll> dep(M), pre(M), post(M); vector<pair<ll, ll>> edges(M); void update(ll a, ll b, ll val) { a+=base-1; b+=base+1; while(a/2 != b/2) { if(a%2==0) Tree[a+1] += val; if(b%2==1) Tree[b-1] += val; a/=2; b/=2; } } ll query(ll x) { x+=base; ll ans = 0; while(x>0) { ans += Tree[x]; x/=2; } return ans; } void dfs(ll v, ll p) { pre[v] = ++nxt; dep[v] = dep[p] + 1; j[v][0] = p; for(ll i=1; i<=maxlog; ++i) j[v][i] = j[j[v][i-1]][i-1]; for(auto u : g[v]) if(u!=p) dfs(u,v); post[v] = ++nxt; } ll lca(ll a, ll b) { if(dep[b] > dep[a]) swap(a,b); for(ll i=maxlog; i>=0; --i) { if(dep[j[a][i]] >= dep[b]) a = j[a][i]; } if(a==b) return a; for(ll i=maxlog; i>=0; --i) { if(j[a][i] != j[b][i]) { a=j[a][i]; b=j[b][i]; } } return j[a][0]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, q; cin >> n >> m >> q; for(ll i=1; i<n; ++i) { ll a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); edges[i] = {a,b}; } dfs(1, 0); for(ll i=1; i<n; ++i) { auto[a,b] = edges[i]; if(dep[a] > dep[b]) swap(edges[i].first, edges[i].second); } vector<pair<ll, ll>> pays; for(ll i=0; i<m; ++i) { ll p,c; cin >> p >> c; pays.push_back({c, edges[p].second}); } sort(pays.begin(), pays.end()); vector<ll> start(q,0), koniec(q,m); vector<ll> s(q), t(q), l(q), gold(q), silver(q); for(ll i=0; i<q; ++i) { cin >> s[i] >> t[i] >> gold[i] >> silver[i]; l[i] = lca(s[i], t[i]); } auto get_sum = [&](ll type) { return query(pre[s[type]]) + query(pre[t[type]]) - 2*query(pre[l[type]]); }; ll ile = 0; while(ile < q) { vector<pair<ll, ll>> sweep; vector<ll> mid(q); for(ll i=0; i<q; ++i) { mid[i] = (start[i] + koniec[i] + 1)/2; sweep.push_back({mid[i], i}); } for(ll i=0; i<m; ++i) { sweep.push_back({i, q}); } sort(sweep.begin(), sweep.end()); Tree.assign(2*base,0); for(auto[czas, type] : sweep) { if(type==q) { auto[c, x] = pays[czas]; update(pre[x], post[x], c); } else { ll suma = get_sum(type); if(suma <= silver[type]) start[type] = mid[type]; else koniec[type] = mid[type]-1; } } ile = 0; for(ll i=0; i<q; ++i) { if(start[i] >= koniec[i]) ile++; } } vector<ll> saved(q); Tree.assign(2*base,0); vector<pair<ll, ll>> sweep; vector<ll> mid(q); for(ll i=0; i<q; ++i) { sweep.push_back({start[i], i}); } for(ll i=0; i<m; ++i) { sweep.push_back({i, q}); } sort(sweep.begin(), sweep.end()); Tree.assign(2*base,0); for(auto[czas, type] : sweep) { if(type==q) { auto[c, x] = pays[czas]; update(pre[x], post[x], 1); } else { saved[type] = get_sum(type); } } for(ll i=0; i<q; ++i) { int uzyte = get_sum(i) - saved[i]; cout << max(-1LL, gold[i] - uzyte) << "\n"; } return 0; }