#include <bits/stdc++.h> using namespace std; #define ll long long #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define SZ(x) ((int) (x).size()) #define ALL(a) (a).begin(), (a).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define left __left #define right __right #define prev __prev #define next __next template <class X, class Y> bool maximize(X &x, Y y) { if (x < y) return x = y, true; else return false; } template <class X, class Y> bool minimize(X &x, Y y) { if (x > y) return x = y, true; else return false; } struct Check { int id, cost; friend istream& operator >> (istream& in, Check &c) { in >> c.id >> c.cost; return in; } bool operator < (const Check &other) const { return (cost < other.cost); } }; struct Query { int s, t; ll gold, silver; friend istream& operator >> (istream& in, Query &q) { in >> q.s >> q.t >> q.gold >> q.silver; return in; } }; struct Edge { int u, v; }; const int LOG = 17; #define MAX_N 100100 int numNode, M, q; int timeDFS = 0; vector<int> adj[MAX_N + 2]; int sta[MAX_N + 2], fin[MAX_N + 2]; int par[LOG + 2][MAX_N + 2]; Edge edges[MAX_N + 2]; Check chk[MAX_N + 2]; Query query[MAX_N + 2]; int Lca[MAX_N + 2], cntQuery[MAX_N + 2], res[MAX_N + 2]; int L[MAX_N + 2], R[MAX_N + 2], G[MAX_N + 2]; struct BIT { ll bit[MAX_N + 2]; int cnt[MAX_N + 2]; int n; void init(int _n) { n = _n; memset(bit, 0, (_n + 2) * sizeof(ll)); memset(cnt, 0, (_n + 2) * sizeof(int)); } void update(int x, int v) { for (; x <= n; x += x & (-x)) { bit[x] += v; cnt[x] += (v > 0 ? 1 : -1); } } void updateRange(int l, int r, int v) { update(l, v); update(r + 1, -v); } int getCnt(int x) { int ans = 0; for (; x > 0; x -= x & (-x)) ans += cnt[x]; return ans; } ll get(int x) { ll ans = 0; for (; x > 0; x -= x & (-x)) ans += bit[x]; return ans; } } fen; void dfs(int u) { sta[u] = ++timeDFS; for (int v : adj[u]) { if (v == par[0][u]) continue; par[0][v] = u; FOR(j, 1, LOG) par[j][v] = par[j - 1][par[j - 1][v]]; dfs(v); } fin[u] = timeDFS; } bool inSubtree(int u, int v) { return (sta[u] <= sta[v] && fin[v] <= fin[u]); } int lca(int u, int v) { if (inSubtree(u, v)) return u; if (inSubtree(v, u)) return v; FORD(i, LOG, 0) if (par[i][u] != 0 && !inSubtree(par[i][u], v)) u = par[i][u]; return par[0][u]; } bool cmp(const int &x, const int &y) { return (G[x] < G[y]); } int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); cin >> numNode >> M >> q; FOR(i, 1, numNode - 1) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); edges[i] = {u, v}; } FOR(i, 1, M) cin >> chk[i]; FOR(i, 1, q) cin >> query[i]; sort(chk + 1, chk + 1 + M); dfs(1); FOR(i, 1, numNode - 1) { if (sta[edges[i].u] > sta[edges[i].v]) swap(edges[i].u, edges[i].v); } FOR(i, 1, q) L[i] = 0, R[i] = M; FOR(i, 1, q) Lca[i] = lca(query[i].s, query[i].t); fen.init(numNode); FOR(i, 1, M) { int id = chk[i].id; int v = edges[id].v; fen.updateRange(sta[v], fin[v], 1); } FOR(i, 1, q) { int u = query[i].s, v = query[i].t; cntQuery[i] = fen.getCnt(sta[u]) + fen.getCnt(sta[v]) - 2 * fen.getCnt(sta[Lca[i]]); res[i] = -1; } while (true) { vector<int> checks; FOR(i, 1, q) if (L[i] <= R[i]) G[i] = (L[i] + R[i]) >> 1, checks.push_back(i); if (checks.empty()) break; sort(ALL(checks), cmp); fen.init(numNode); int ptr = 1; for (int id : checks) { while (ptr <= G[id]) { int idEdge = chk[ptr].id; int v = edges[idEdge].v; fen.updateRange(sta[v], fin[v], chk[ptr].cost); ++ptr; } /// getResults; int u = sta[query[id].s], v = sta[query[id].t], r = sta[Lca[id]]; ll totalVal = fen.get(u) + fen.get(v) - 2 * fen.get(r); int totalCnt = fen.getCnt(u) + fen.getCnt(v) - 2 * fen.getCnt(r); if (totalVal <= query[id].silver) { L[id] = G[id] + 1; if (cntQuery[id] - totalCnt <= query[id].gold) { res[id] = query[id].gold - (cntQuery[id] - totalCnt); } } else R[id] = G[id] - 1; } } FOR(i, 1, q) cout << res[i] << "\n"; return 0; }