#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll>> graph[100002];
vector<ll> bramki[100002];
ll dep[100002];
pair<ll, ll> par[100002];
void dfs(ll v, ll p)
{
for (auto [u, ind] : graph[v])
{
if (u == p)
continue;
par[u] = {v, ind};
dep[u] = dep[v] + 1;
dfs(u, v);
}
}
ll zap(ll v, ll u, ll x, ll y)
{
vector<ll> costs;
if (dep[v] > dep[u])
swap(v, u);
while (dep[v] < dep[u])
{
for (auto x : bramki[par[u].second])
costs.push_back(x);
u = par[u].first;
}
while (v != u)
{
for (auto x : bramki[par[u].second])
costs.push_back(x);
for (auto x : bramki[par[v].second])
costs.push_back(x);
v = par[v].first;
u = par[u].first;
}
sort(costs.begin(),costs.end(),greater<ll>());
while(costs.size() && y>=costs.back()){
y-=costs.back();
costs.pop_back();
}
if (x < (ll)costs.size())return -1;
else return x - costs.size();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, m, q;
cin >> n >> m >> q;
for (ll i = 1, a, b; i < n; i++)
{
cin >> a >> b;
graph[a].push_back({b, i});
graph[b].push_back({a, i});
}
for (ll i = 1, p, c; i <= m; i++)
{
cin >> p >> c;
bramki[p].push_back(c);
}
dfs(1, 0);
for (ll i = 1, a, b, x, y; i <= q; i++)
{
cin >> a >> b >> x >> y;
cout << zap(a, b, x, y) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |