#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) a.begin(),a.end() typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef unsigned long long ull; template<const int MOD> struct mint{ int val; constexpr mint(int x = 0) : val((x%=MOD) + (x<0?MOD:0)) {;} mint& operator+=(const mint &b){val+=b.val; val-=MOD*(val>=MOD); return *this;} mint& operator-=(const mint &b){val-=b.val; val+=MOD*(val<0); return *this;} mint& operator*=(const mint &b){val=1ll*val*b.val%MOD; return *this;} mint& operator/=(const mint &b){return *this *= b.inv();} mint inv() const { int x = 1, y = 0, t; for(int a=val, b=MOD; b; swap(a,b), swap(x,y)) t = a/b, a-=t*b, x-=t*y; return mint(x); } mint pow(int b) const{ if(b<0) b += MOD-1; mint a = *this, res(1); for(; b>0; a*=a, b>>=1) if(b&1) res *= a; return res; } friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; } friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; } friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; } friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; } friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; } friend bool operator!=(const mint &a, const mint &b) { return a.val != b.val; } friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; } friend ostream& operator<<(ostream &os, const mint &a) { return os << a.val; } }; const int mxn = 1e5+1, mxa = 18e5, lg2 = 17; vector<pii> g[mxn]; vector<int> check[mxn]; int tin[mxn], tout[mxn], tim = 0; int suc[mxn][lg2], dep[mxn]; int sz[mxa], pl[mxa], pr[mxa], node = 0; int pos[mxn], root[mxn], len; ll st[mxa]; int update(int cur, int l, int r, int k){ int id = ++node; if(l==r){st[id]=st[cur]+pos[l],sz[id]=sz[cur]+1; return id;} int m = (l+r)>>1; if(k <= m) pl[id] = update(pl[cur],l,m,k), pr[id] = pr[cur]; else pr[id] = update(pr[cur],m+1,r,k), pl[id] = pl[cur]; st[id] = st[pl[id]] + st[pr[id]]; sz[id] = sz[pl[id]] + sz[pr[id]]; return id; } void dfs(int u, int p){ tin[u] = ++tim; suc[u][0] = p; for(int i = 1; i < lg2; i++) suc[u][i] = suc[suc[u][i-1]][i-1]; for(auto [v,i] : g[u]) if(v!=p){ root[v] = root[u]; dep[v] = dep[u]; for(auto c : check[i]){ c = lower_bound(pos,pos+len,c)-pos; root[v] = update(root[v],0,len-1,c); dep[v]++; } dfs(v,u); } tout[u] = tim; } bool is_anc(int u, int v){ return tin[u]<=tin[v] && tout[v]<=tout[u]; } int get_lca(int u, int v){ if(is_anc(u,v)) return u; if(is_anc(v,u)) return v; for(int i = lg2-1; i >= 0; i--) if(!is_anc(suc[u][i],v)) u = suc[u][i]; return suc[u][0]; } ll get(int u, int v, int lca, int l, int r, ll rem){ if(l==r){ ll cur = st[u]+st[v]-2*st[lca]; if(cur <= rem) return sz[u]+sz[v]-2*sz[lca]; else return rem/pos[l]; } int m = (l+r)>>1; ll cur = st[pl[u]] + st[pl[v]] - 2*st[pl[lca]]; if(cur >= rem) return get(pl[u],pl[v],pl[lca],l,m,rem); else return get(pr[u],pr[v],pr[lca],m+1,r,rem - cur) + sz[pl[u]] + sz[pl[v]] - 2*sz[pl[lca]]; } void solve(){ int n,k,q; cin >> n >> k >> q; for(int i = 1; i < n; i++){ int u,v; cin >> u >> v; g[u].pb({v,i}); g[v].pb({u,i}); } for(int i = 1; i <= k; i++){ int p,c; cin >> p >> c; check[p].pb(c); pos[i] = c; } sort(pos,pos+k+1); len = unique(pos,pos+k+1)-pos; dfs(1,1); for(int _ = 0; _ < q; _++){ int u,v,x; ll y; cin >> u >> v >> x >> y; int lca = get_lca(u,v); ll sum = get(root[u],root[v],root[lca],0,len-1,y); cout << max((ll)-1, x - (dep[u]+dep[v]-2*dep[lca]-sum)) << '\n'; } } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }