#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; vector<pii> g[mxn]; vector<int> check[mxn]; vector<int> vec[mxn]; int dep[mxn], par[mxn]; int qu[mxn][4]; ll qu2[mxn]; bool vis[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; } int find(int u){ if(par[u]<0) return u; return par[u]=find(par[u]); } void dfs(int u, int p){ vis[u] = 1; par[u] = -1; for(auto i : vec[u]){ int v = qu[i][0]^qu[i][1]^u; if(vis[v]) qu[i][3] = find(v); } 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); par[v] = u; } } int 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].emplace_back(pii{v,i}); g[v].emplace_back(pii{u,i}); } for(int i = 1; i <= k; i++){ int p,c; cin >> p >> c; check[p].emplace_back(c); pos[i] = c; } sort(pos,pos+k+1); len = unique(pos,pos+k+1)-pos; for(int i = 1; i <= q; i++){ cin >> qu[i][0] >> qu[i][1] >> qu[i][2] >> qu2[i]; vec[qu[i][0]].emplace_back(i); vec[qu[i][1]].emplace_back(i); } dfs(1,1); for(int i = 1; i <= q; i++){ int u = qu[i][0], v = qu[i][1], lca = qu[i][3]; cout << max(-1, qu[i][2] - (dep[u]+dep[v]-2*dep[lca] - get(root[u],root[v],root[lca],0,len-1,qu2[i]))) << '\n'; } } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }