#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 100000 + 7;
const int K = 20;
int n;
int m;
int q;
vector<int> g[N];
pair<int, int> edges[N];
int dep[N];
int par[N];
int l[N];
int r[N];
int tab[K][N];
int tt = 0;
pair<int, int> updates[N];
struct Node {
Node* l;
Node* r;
ll sum;
ll lazy;
Node(Node* lll = NULL, Node *rr = NULL, ll ssum = 0, ll llazy = 0) {
l = lll;
r = rr;
sum = ssum;
lazy = llazy;
}
};
Node* sum[N];
Node* cnt[N];
void push(Node* &root, int tl, int tr) {
assert(root != NULL);
if (tl < tr) {
assert(root->l != NULL);
assert(root->r != NULL);
root->l = new Node(root->l->l, root->l->r, root->l->sum, root->l->lazy + root->lazy);
root->r = new Node(root->r->l, root->r->r, root->r->sum, root->r->lazy + root->lazy);
}
root = new Node(root->l, root->r, root->sum + root->lazy, 0);
}
void build(Node* &root, int tl, int tr) {
root = new Node();
if (tl < tr) {
int tm = (tl + tr) / 2;
build(root->l, tl, tm);
build(root->r, tm + 1, tr);
}
}
void print(Node* root, int v = 1) {
cout << v << "\n";
if (root->l != NULL) {
print(root->l, 2 * v);
}
if (root->r != NULL) {
print(root->r, 2 * v + 1);
}
}
void update(Node* &root, Node* old, int tl, int tr, int x, int y, ll val) {
push(root, tl, tr);
if (x <= tl && tr <= y) {
root = new Node(root->l, root->r, root->sum, root->lazy + val);
push(root, tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (x <= tm && y <= tm) {
root->r = old->r;
update(root->l, old->l, tl, tm, x, y, val);
} else if (tm + 1 <= x && tm + 1 <= y) {
root->l = old->l;
update(root->r, old->r, tm + 1, tr, x, y, val);
} else {
update(root->l, old->l, tl, tm, x, tm, val);
update(root->r, old->r, tm + 1, tr, tm + 1, y, val);
}
push(root->l, tl, tm);
push(root->r, tm + 1, tr);
root->sum = root->l->sum + root->r->sum;
}
ll query(Node* &root, int tl, int tr, int x, int y) {
push(root, tl, tr);
if (x <= tl && tr <= y) {
return root->sum;
}
int tm = (tl + tr) / 2;
if (x <= tm && y <= tm) {
return query(root->l, tl, tm, x, y);
} else if (tm + 1 <= x && tm + 1 <= y) {
return query(root->r, tm + 1, tr, x, y);
} else {
return query(root->l, tl, tm, x, tm) + query(root->r, tm + 1, tr, tm + 1, y);
}
}
int get(Node* &root, int x) {
return query(root, 1, n, l[x], l[x]);
}
void build(int a, int p = 0) {
l[a] = ++tt;
tab[0][a] = p;
for (int k = 1; k < K; k++) {
tab[k][a] = tab[k - 1][tab[k - 1][a]];
}
for (auto &b : g[a]) {
if (b != p) {
par[b] = a;
dep[b] = dep[a] + 1;
build(b, a);
}
}
r[a] = tt;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (int k = K - 1; k >= 0; k--) {
if (dep[x] - (1 << k) >= dep[y]) {
x = tab[k][x];
}
}
if (x == y) {
return x;
}
for (int k = K - 1; k >= 0; k--) {
if (tab[k][x] != tab[k][y]) {
x = tab[k][x];
y = tab[k][y];
}
}
return tab[0][x];
}
bool is_ancestor(int x, int y) { /// x ancestor of y
return l[x] <= l[y] && r[y] <= r[x];
}
ll get_sum(int when, int x, int y) {
int z = lca(x, y);
return get(sum[when], x) + get(sum[when], y) - 2 * get(sum[when], z);
}
ll get_count(int when, int x, int y) {
int z = lca(x, y);
return get(cnt[when], x) + get(cnt[when], y) - 2 * get(cnt[when], z);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/// freopen("input.txt", "r", stdin);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
edges[i] = {x, y};
}
build(1);
for (int i = 1; i <= m; i++) {
ll road, val;
cin >> road >> val;
int x = edges[road].first;
int y = edges[road].second;
if (dep[x] < dep[y]) {
swap(x, y);
}
updates[i] = {val, x};
}
sort(updates + 1, updates + m + 1);
{ /// for sum
Node* root = new Node();
build(root, 1, n);
/// print(root);
sum[0] = root;
for (int i = 1; i <= m; i++) {
int val = updates[i].first;
int x = updates[i].second;
sum[i] = root;
update(sum[i], root, 1, n, l[x], r[x], val);
root = sum[i];
}
}
{ /// for cnt
Node* root = new Node();
build(root, 1, n);
cnt[0] = root;
for (int i = 1; i <= m; i++) {
int val = updates[i].first;
int x = updates[i].second;
cnt[i] = root;
update(cnt[i], root, 1, n, l[x], r[x], 1);
root = cnt[i];
}
}
while (q--) {
ll s, t, x, y;
cin >> s >> t >> x >> y;
int low = 1, high = m, sol = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (get_sum(mid, s, t) <= y) {
sol = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
int z = lca(s, t);
int payed = get_count(sol, s, t);
int total = get_count(m, s, t);
int keep = x - (total - payed);
if (keep < 0) {
keep = -1;
}
cout << keep << "\n";
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:206:11: warning: unused variable 'val' [-Wunused-variable]
206 | int val = updates[i].first;
| ^~~
currencies.cpp:227:9: warning: unused variable 'z' [-Wunused-variable]
227 | int z = lca(s, t);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 3 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 4 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 5 |
Incorrect |
81 ms |
114260 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 2 |
Incorrect |
133 ms |
169140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
144 ms |
171224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 3 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 4 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 5 |
Incorrect |
81 ms |
114260 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
