#include <iostream> #include <vector> #include <map> using namespace std; #define int long long const int N = (1<<17) + 1; vector<pair<int, int>> nei[N]; vector<int> vec[N]; int Par[N][20], hei[N], inv[N], cur; map<int, int> mp, mp2; struct node{ node *lc, *rc; int cnt = 0, sum = 0; } *seg[N<<1]; node* insert(node* cur, int t, int i, int v, int st = 1, int en = N){ if (i >= en or i < st) return cur; node* nw = new node(); if (en - st == 1){ nw->cnt = cur->cnt + t; nw->sum = cur->sum + t * v; return nw; } int mid = (st + en) / 2; nw->lc = insert(cur->lc, t, i, v, st, mid); nw->rc = insert(cur->rc, t, i, v, mid, en); nw->sum = nw->lc->sum + nw->rc->sum; nw->cnt = nw->lc->cnt + nw->rc->cnt; return nw; } int get(node *cur, int k, int st = 1, int en = N){ if (k == 0) return 0; if (en - st == 1) return cur->sum; int mid = (st + en) / 2; if (k < mid) return get(cur->lc, k, st, mid); return get(cur->rc, k, mid, en) + cur->lc->sum; } int getCnt(node *cur, int k, int st = 1, int en = N){ if (k == 0) return 0; if (en - st == 1) return cur->cnt; int mid = (st + en) / 2; if (k < mid) return getCnt(cur->lc, k, st, mid); return getCnt(cur->rc, k, mid, en) + cur->lc->cnt; } node* build(int n){ // cout<<n<<endl; node *nw = new node(); if (n == 1) return nw; nw->lc = build(n / 2); nw->rc = build(n / 2); return nw; } void dfs(int u, int p){ Par[u][0] = p; hei[u] = hei[p] + 1; for (int i=0;i<17;i++) Par[u][i+1] = Par[Par[u][i]][i]; for (auto [i, id] : nei[u]){ if (i == p) continue; seg[i] = insert(seg[u], 1, 0, 0); for (int j : vec[id]) seg[i] = insert(seg[i], 1, mp2[j], j); dfs(i, u); } } int LCA(int u, int v){ if (hei[u] > hei[v]) swap(u, v); for (int i=17; i+1; i--){ if ((1<<i) + hei[u] <= hei[v]) v = Par[v][i]; } for (int i=17; i+1; i--){ if (Par[u][i] != Par[v][i]) u = Par[u][i], v = Par[v][i]; } return (u == v ? u : Par[v][0]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, q; cin>>n>>m>>q; for (int i=1, a, b;i<n;i++){ cin>>a>>b; nei[a].push_back({b, i}); nei[b].push_back({a, i}); } for (int i=1, p, c;i<=m;i++){ cin>>p>>c; vec[p].push_back(c); mp[c]; } for (auto [i, j] : mp) mp2[i] = ++cur, inv[cur] = i; // cout<<"done"<<endl; seg[1] = build(N); dfs(1, 0); // return 0; inv[cur + 1] = 1e18; for (int i=1;i<=q;i++){ int s, t, x, y; cin>>s>>t>>x>>y; int lca = LCA(s, t); int l = 0, r = cur + 1; while (l + 1 < r){ int mid = (l + r) / 2, k = get(seg[s], mid) + get(seg[t], mid) - 2 * get(seg[lca], mid); // cout<<mid<<" "<<get(seg[s], mid)<<" "<<get(seg[t], mid)<<" "<<get(seg[lca], mid)<<endl; if (k <= y) l = mid; else r = mid; } // cout<<s<<" "<<t<<" "<<lca<<endl; int c1 = seg[s]->cnt + seg[t]->cnt - 2 * seg[lca]->cnt; int c2 = getCnt(seg[s], r) + getCnt(seg[t], r) - 2 * getCnt(seg[lca], r); int c3 = getCnt(seg[s], r-1) + getCnt(seg[t], r-1) - 2 * getCnt(seg[lca], r-1); // cout<<"done"<<endl; c1 -= c2; c2 -= c3; y -= get(seg[s], l) + get(seg[t], l) - 2 * get(seg[lca], l); // cout<<"done"<<endl; // cout<<l<<" "<<r<<" "<<inv[r]<<" "<<y<<endl; c2 -= min(c2, y / inv[r]); // cout<<"done"<<endl; if (x < c1 + c2) cout<<-1<<'\n'; else cout<<x - c1 - c2<<'\n'; } } /* 10 7 9 1 8 6 3 5 9 7 9 3 1 3 4 10 1 2 6 5 6 9 4 7 4 7 4 2 4 7 4 7 4 1 4 8 6 5 3 3 9 8 0 4 7 6 15 7 4 9 3 6 4 8 0 9 10 5 16 5 3 2 4 2 8 4 3 6 1 3 3 */