#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100010
#define MIN first
#define MAXNUM second
using namespace std;
using ll = long long;
int n, m, q;
int par[20][MAX], depth[MAX], in[MAX], out[MAX];
int max_h;
int dstep[MAX];
vector<int> graph[MAX];
int i, j;
struct spt {
int s, e, val;
bool operator<(const spt& x) { return val < x.val; }
};
struct qu {
int s, t, x, y;
};
vector<spt> v_spt;
vector<qu> v_q;
int l[MAX], r[MAX];
vector<pair<int, int>> arr;
void fastIO() {
ios::sync_with_stdio(false); cin.tie(0);
}
//euler tour trick.
int i_ett, i_order;
void ETT(int curr, int dep) {
dstep[curr] = ++i_order; in[curr] = ++i_ett; depth[curr] = dep;
for (int next : graph[curr]) {
if (in[next]) continue;
par[0][next] = curr;
ETT(next, dep + 1);
}
i_ett++;
out[curr] = i_ett;
}
//get parent based on sparse table.
void getParent() {
int tmp = n, cnt = 0;
while (tmp > 1) { tmp >>= 1; cnt++; }
max_h = cnt;
for (int h = 1; h <= max_h; h++) {
for (int x = 2; x <= n; x++) {
if (par[h - 1][x]) { par[h][x] = par[h - 1][par[h - 1][x]]; }
}
}
}
int getLCA(int a, int b) {
if (depth[a] != depth[b]) {
if (depth[a] < depth[b]) { swap(a, b); }
int diff = depth[a] - depth[b];
for (j = 0; diff > 0; j++) {
if (diff & 1) { a = par[j][a]; }
diff >>= 1;
}
}
if (a != b) {
for (int k = max_h; k >= 0; k--) {
if (par[k][a] != 0 && par[k][a] != par[k][b]) {
a = par[k][a]; b = par[k][b];
}
}
a = par[0][a];
}
return a;
}
ll tree_cpt[8 * MAX], tree_first[8 * MAX], tree_cnt[8 * MAX];
void update(ll tree[], int curr, int start, int end, int idx, ll val) {
if (start == end) { tree[curr] += val; return; }
int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
if (idx <= mid) { update(tree, lidx, start, mid, idx, val); }
else { update(tree, ridx, mid + 1, end, idx, val); }
tree[curr] = tree[lidx] + tree[ridx];
}
ll getSum(ll tree[], int curr, int start, int end, int t_start, int t_end) {
if (end < t_start || t_end < start) { return 0; }
if (t_start <= start && end <= t_end) { return tree[curr]; }
int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
return getSum(tree, lidx, start, mid, t_start, t_end) + getSum(tree, ridx, mid + 1, end, t_start, t_end);
}
void reset(int start = 1, int end = i_ett, int curr = 1) {
tree_cpt[curr] = tree_cnt[curr] = 0;
if (start == end) { return; }
int mid = start + end >> 1;
reset(start, mid, curr << 1);
reset(mid + 1, end, curr << 1 | 1);
}
int ret[MAX], sum_sp[MAX], sum_cnt[MAX];
void input() {
cin >> n >> m >> q;
arr.resize(n);
int a, b;
for (i = 1; i <= n - 1; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
arr[i] = { min(a, b), max(a,b) };
}
for (i = 1; i <= m; i++) {
cin >> a >> b;
v_spt.push_back({ arr[a].MIN, arr[a].MAXNUM, b });
}
sort(v_spt.begin(), v_spt.end());
v_q.resize(q);
for (i = 0; i < q; i++) {
cin >> v_q[i].s >> v_q[i].t >> v_q[i].x >> v_q[i].y;
}
}
void solve() {
for (i = 0; i < MAX; i++) { ret[i] = -1; }
ETT(1, 0);
getParent();
//pbs
for (i = 0; i < q; i++) { l[i] = -1, r[i] = m; }
for (i = 0; i < m; i++) {
int start = v_spt[i].s, end = v_spt[i].e;
if (in[end] <= in[start] && in[start] <= out[end]) swap(start, end);
update(tree_first, 1, 1, i_ett, in[end], 1);
update(tree_first, 1, 1, i_ett, out[end], -1);
}
for (i = 0; i < q; i++) {
int lca = getLCA(v_q[i].s, v_q[i].t);
sum_sp[i] = getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].s])
+ getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].t])
- 2 * getSum(tree_first, 1, 1, i_ett, 1, in[lca]);
}
while (true) {
for (i = 0; i < MAX; i++) {
graph[i].clear();
}
reset();
bool flag = false;
for (i = 0; i < q; i++) {
if (l[i] + 1 == r[i]) continue;
flag = true; graph[l[i] + r[i] >> 1].push_back(i);
}
if (!flag) break;
for (i = 0; i < m; i++) {
int start = v_spt[i].s, end = v_spt[i].e, v = v_spt[i].val;
if (in[end] <= in[start] && in[start] <= out[end]) { swap(start, end); }
update(tree_cpt, 1, 1, i_ett, in[end], v);
update(tree_cpt, 1, 1, i_ett, out[end], -v);
update(tree_cnt, 1, 1, i_ett, in[end], 1);
update(tree_cnt, 1, 1, i_ett, out[end], -1);
for (int next : graph[i]) {
int lca = getLCA(v_q[next].s, v_q[next].t);
ll currSp = getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].s])
+ getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].t])
- 2 * getSum(tree_cpt, 1, 1, i_ett, 1, in[lca]);
ll currCnt = getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].s])
+ getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].t])
- 2 * getSum(tree_cnt, 1, 1, i_ett, 1, in[lca]);
if (currSp <= v_q[next].y) {
ret[next] = max((ll)ret[next], v_q[next].x - sum_sp[next] + currCnt);
l[next] = i;
}
else { r[next] = i; }
}
}
}
for (i = 0; i < q; i++) {
if (ret[i] == -1 && v_q[i].x >= sum_sp[i]) {
ret[i] = v_q[i].x - sum_sp[i];
}
cout << ret[i] << '\n';
}
}
int main() {
fastIO();
input();
solve();
return 0;
}
Compilation message
currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:84:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'll getSum(ll*, int, int, int, int, int)':
currencies.cpp:93:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'void reset(int, int, int)':
currencies.cpp:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:161:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | flag = true; graph[l[i] + r[i] >> 1].push_back(i);
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 5 |
Incorrect |
9 ms |
12892 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
15236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 5 |
Incorrect |
9 ms |
12892 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
