#include<bits/stdc++.h>
using namespace std;
#define int long long
const int LG = 20;
int N, M, Q;
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> adj;
vector<array<int, LG>> par;
vector<int> lvl, pp, cnt;
void dfs(int s) {
for(auto& v : adj[s]) {
int u = v.first;
if(u == par[s][0]) continue;
lvl[u] = lvl[s] + 1;
par[u][0] = s;
for(int i = 1; i < LG; ++i) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
dfs(u);
}
}
int lca(int s, int t) {
if(lvl[t] > lvl[s]) swap(s, t);
for(int i = LG - 1; i >= 0; --i) {
if(lvl[par[s][i]] >= lvl[t]) {
s = par[s][i];
}
}
if(s == t) return s;
for(int i = LG - 1; i >= 0; --i) {
if(par[s][i] != par[t][i]) {
s = par[s][i];
t = par[t][i];
}
}
return par[s][0];
}
void dfs0(int s) {
for(auto& v : adj[s]) {
int u = v.first;
if(u == par[s][0]) continue;
cnt[u] = cnt[s] + pp[u];
dfs(u);
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> Q;
adj.resize(N);
for(int i = 1; i < N; ++i) {
int u, v; cin >> u >> v;
--u; --v;
e.emplace_back(u, v);
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
lvl.resize(N);
par.resize(N);
dfs(0);
for(int i = 0; i + 1 < N; ++i) {
if(par[e[i].second][0] == e[i].first) {
swap(e[i].first, e[i].second);
}
}
pp.resize(N);
int c;
for(int i = 0; i < M; ++i) {
int p; cin >> p >> c;
--p;
++pp[e[p].first];
}
cnt.resize(N);
dfs0(0);
while(Q--) {
int S, T, X;
long long Y;
cin >> S >> T >> X >> Y;
--S; --T;
int L = lca(S, T);
int many = cnt[S] + cnt[T] + 2 * cnt[L] - Y / c;
int ans = X - many;
if(ans < 0) {
cout << "-1\n";
} else {
cout << ans << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
