#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const ll INF = 4e18; // A large value representing infinity
const int MAXN = 100005;
const int MAXQ = 100005;
struct Query {
int id;
int s, t;
ll x, y;
};
// Graph and checkpoint data
vector<pair<int, int>> adj[MAXN];
vector<ll> road_checkpoints[MAXN];
vector<Query> all_queries;
int N, M, Q;
ll final_ans[MAXQ];
// --- Centroid Decomposition Structures ---
int subtree_size[MAXN];
bool is_removed[MAXN];
// Structures to hold path info relative to the current centroid
struct PathInfo {
vector<ll> costs;
vector<ll> p_sums;
};
map<int, PathInfo> path_info_map; // node -> path info from centroid
int sub_parent[MAXN];
// --- Centroid Decomposition Core Logic ---
void dfs_size(int u, int p) {
subtree_size[u] = 1;
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !is_removed[v]) {
dfs_size(v, u);
subtree_size[u] += subtree_size[v];
}
}
}
int find_centroid(int u, int p, int total_size) {
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !is_removed[v] && subtree_size[v] * 2 > total_size) {
return find_centroid(v, u, total_size);
}
}
return u;
}
// Optimized DFS to generate path info from the centroid
void dfs_path_gen(int u, int p, int root_node, vector<ll>& current_costs) {
sub_parent[u] = root_node;
// Store the path info for the current node 'u'
path_info_map[u].costs = current_costs;
path_info_map[u].p_sums.assign(current_costs.size() + 1, 0);
for (size_t i = 0; i < current_costs.size(); ++i) {
path_info_map[u].p_sums[i + 1] = path_info_map[u].p_sums[i] + current_costs[i];
}
// Recurse to children
for (auto& edge : adj[u]) {
int v = edge.first;
int road_idx = edge.second;
if (v != p && !is_removed[v]) {
size_t original_size = current_costs.size();
current_costs.insert(current_costs.end(), road_checkpoints[road_idx].begin(), road_checkpoints[road_idx].end());
inplace_merge(current_costs.begin(), current_costs.begin() + original_size, current_costs.end());
dfs_path_gen(v, u, root_node, current_costs);
// Backtrack
current_costs.resize(original_size);
}
}
}
// Calculates min silver cost to pay for k_silver checkpoints from two paths
ll calculate_min_silver(const PathInfo& s_info, const PathInfo& t_info, int k_silver) {
if (k_silver < 0) return 0;
if (k_silver > s_info.costs.size() + t_info.costs.size()) return INF;
ll min_cost = INF;
const auto& ps_s = s_info.p_sums;
const auto& ps_t = t_info.p_sums;
for (int i = 0; i <= s_info.costs.size(); ++i) {
int j = k_silver - i;
if (j >= 0 && j <= t_info.costs.size()) {
min_cost = min(min_cost, ps_s[i] + ps_t[j]);
}
}
return min_cost;
}
// The main "checker" function using Centroid Decomposition
void solve(int entry_node, vector<Query>& queries, int mid_gold, vector<bool>& results) {
if (queries.empty()) return;
dfs_size(entry_node, 0);
int centroid = find_centroid(entry_node, 0, subtree_size[entry_node]);
// Efficiently compute path info for all nodes in the component
path_info_map.clear();
sub_parent[centroid] = centroid;
vector<ll> empty_costs;
dfs_path_gen(centroid, 0, centroid, empty_costs);
// Partition queries
map<int, vector<Query>> sub_queries;
vector<Query> crossing_queries;
for (auto& q : queries) {
if (sub_parent[q.s] == sub_parent[q.t]) {
if (sub_parent[q.s] != centroid) {
sub_queries[sub_parent[q.s]].push_back(q);
} else {
crossing_queries.push_back(q);
}
} else {
crossing_queries.push_back(q);
}
}
// Process queries that cross the centroid
for (auto& q : crossing_queries) {
const auto& s_info = path_info_map[q.s];
const auto& t_info = path_info_map[q.t];
int p_checkpoints = s_info.costs.size() + t_info.costs.size();
int k_silver = p_checkpoints - mid_gold;
if (k_silver < 0) {
results[q.id] = true;
} else {
ll silver_needed = calculate_min_silver(s_info, t_info, k_silver);
if (silver_needed <= q.y) {
results[q.id] = true;
}
}
}
// Recurse on subproblems
is_removed[centroid] = true;
for (auto & [sub_root, qs] : sub_queries) {
solve(sub_root, qs, mid_gold, results);
}
}
// --- Parallel Binary Search ---
void pbs(vector<Query>& queries, int min_gold, int max_gold) {
if (queries.empty() || min_gold > max_gold) {
return;
}
int mid_gold = min_gold + (max_gold - min_gold) / 2;
vector<Query> possible_qs, impossible_qs;
fill(is_removed + 1, is_removed + N + 1, false);
vector<bool> results(Q, false);
solve(1, queries, mid_gold, results);
for (const auto& q : queries) {
if (results[q.id]) {
final_ans[q.id] = mid_gold;
possible_qs.push_back(q);
} else {
impossible_qs.push_back(q);
}
}
pbs(possible_qs, min_gold, mid_gold - 1);
pbs(impossible_qs, mid_gold + 1, max_gold);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> Q;
for (int i = 1; i < N; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for (int i = 0; i < M; ++i) {
int p;
ll c;
cin >> p >> c;
road_checkpoints[p].push_back(c);
}
for (int i = 1; i < N; ++i) {
sort(road_checkpoints[i].begin(), road_checkpoints[i].end());
}
for (int i = 0; i < Q; ++i) {
int s, t;
ll x, y;
cin >> s >> t >> x >> y;
all_queries.push_back({i, s, t, x, y});
}
fill(final_ans, final_ans + Q, -1);
pbs(all_queries, 0, M); // Max possible gold spent is M
for (int i = 0; i < Q; ++i) {
ll gold_spent = final_ans[i];
if (gold_spent != -1 && all_queries[i].x >= gold_spent) {
cout << all_queries[i].x - gold_spent << "\n";
} else {
cout << -1 << "\n";
}
}
return 0;
}
