#include <bits/stdc++.h>
#define ff first
#define ss second
#define sz size()
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100005;
// const int mod = 1e9+7;
// ll bigmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll depth[N], l, r, n, q[N], a[N], o, ind[N];
ll baha[N], mm, qq;
ll dp1[N][21], dp[N][21], val, cnt[N], jog, tt;
pair <ll, ll> p[N];
vector <pair <ll, ll>> v[N];
void dfs(int x, int y, int par, ll bal) {
depth[x] = y;
o++;
q[o] = x;
if (par != 0) {
baha[x] = bal + baha[par];
}
for (auto i : v[x]) {
if (i.ff != par) {
dfs (i.ff, y + 1, x, i.ss);
if (q[o] != x) {
o++;
q[o] = x;
}
}
}
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
// freopen("ibnput.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// clock_t tStart = clock();
// printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
cin >> n >> mm >> qq;
for (int i = 1; i < n; ++i) {
cin >> p[i].ff >> p[i].ss;
}
for (int i = 1; i <= mm; ++i) {
cin >> l >> r;
val = r;
cnt[l]++;
}
for (int i = 1; i < n; ++i) {
v[p[i].ff].pb ({p[i].ss, cnt[i]});
v[p[i].ss].pb ({p[i].ff, cnt[i]});
}
dfs (1, 1, 0, 0);
for (int i = 1; i <= o; ++i) {
a[i] = depth[q[i]];
if (!ind[q[i]]) ind[q[i]] = i;
}
for (int i = 0; i <= 16; ++i) {
dp[0][i] = 1e9;
for (int j = 1; j <= o; ++j) {
if (i == 0) {
dp[j][i] = a[j];
dp1[j][i] = q[j];
}
else {
int x = (1 << (i - 1));
if (dp[j][i - 1] > dp[j + x][i - 1]) {
dp[j][i] = dp[j + x][i - 1];
dp1[j][i] = dp1[j + x][i - 1];
}
else {
dp[j][i] = dp[j][i - 1];
dp1[j][i] = dp1[j][i - 1];
}
}
}
}
while ( qq-- ) {
ll gold, silver;
cin >> l >> r >> gold >> silver;
int l1 = l;
int r1 = r;
l = ind[l];
r = ind[r];
if (l > r) swap (l, r);
int x = log2(r - l);
int y = (1 << x);
if (dp[l][x] > dp[r - y][x]) {
jog = dp1[r - y][x];
}
else {
jog = dp1[l][x];
}
// jog
ll jog1 = baha[l1] + baha[r1] - (2 * baha[jog]);
jog1 -= (silver / val);
if (jog1 <= gold) {
cout << gold - jog1 << "\n";
}
else cout << "-1\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
