#include <bits/stdc++.h>
using namespace std;
typedef long long 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];
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];
}
struct PST {
struct Node {
int left, right, old;
int x, upd;
Node() {
left = right = old = x = upd = 0;
}
};
vector<Node> t;
vector<int> vers;
int n, cnt;
PST(int n) {
vers.push_back(1);
t.resize((int)2e6);
cnt = 2;
this->n = n;
}
int nw() {
//ms.push_back(tree());
return cnt++;
}
int clone(int b) {
int a = nw();
t[a].left = t[b].left;
t[a].right = t[b].right;
t[a].old = b;
t[a].x = t[b].x;
return a;
}
void addleft(int root, bool tr) {
if (t[root].left == 0) {
t[root].left = nw();
} else if (tr || t[root].left == t[t[root].old].left) {
t[root].left = clone(t[root].left);
}
}
void addright(int root, bool tr) {
if (t[root].right == 0) {
t[root].right = nw();
} else if (tr || t[root].right == t[t[root].old].right) {
t[root].right = clone(t[root].right);
}
}
void push(int root, int l, int r) {
if (t[root].upd == 0) {
return;
}
if (l == r) {
t[root].x += t[root].upd;
t[root].upd = 0;
return;
}
addleft(root, 0);
addright(root, 0);
t[t[root].left].upd += t[root].upd;
t[t[root].right].upd += t[root].upd;
t[root].x += t[root].upd * (r - l + 1);
t[root].upd = 0;
}
bool prov(int l, int r, int l1, int r1) {
return l1 > r || r1 < l;
}
int sum(int root, int l, int r, int l1, int r1) {
if (prov(l, r, l1, r1) || !root) {
return 0;
}
push(root, l, r);
if (l == l1 && r == r1) {
return t[root].x;
}
int m = (l + r) / 2;
int x = sum(t[root].left, l, m, l1, min(m, r1));
int y = sum(t[root].right, m + 1, r, max(m + 1, l1), r1);
return x + y;
}
void upd(int root, int l, int r, int l1, int r1, int x) {
push(root, l, r);
if (l == l1 && r == r1) {
t[root].upd += x;
push(root, l, r);
return;
}
int m = (l + r) / 2;
if (!prov(l, m, l1, min(m, r1))) {
addleft(root, 1);
upd(t[root].left, l, m, l1, min(m, r1), x);
}
if (!prov(m + 1, r, max(m + 1, l1), r1)) {
addright(root, 1);
upd(t[root].right, m + 1, r, max(l1, m + 1), r1, x);
}
t[root].x = t[t[root].left].x + t[t[root].right].x;
}
int sum(int l, int r) {
return sum(vers.back(), 1, n, l, r);
}
int sum(int s, int l, int r) {
return sum(vers[s], 1, n, l, r);
}
int sum(int s1, int s2, int l, int r) {
return sum(s2, l, r) - sum(s1, l, r);
}
void upd(int l, int r, int x) {
vers.push_back(clone(vers.back()));
upd(vers.back(), 1, n, l, r, x);
}
};
PST tree1(N), tree2(N);
int get_sum(int when, int x, int y) {
int z = lca(x, y);
return tree1.sum(when, l[x], l[x]) + tree1.sum(when, l[y], l[y]) - 2 * tree1.sum(when, l[z], l[z]);
}
int get_count(int when, int x, int y) {
int z = lca(x, y);
return tree2.sum(when, l[x], l[x]) + tree2.sum(when, l[y], l[y]) - 2 * tree2.sum(when, l[z], l[z]);
}
int 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
for (int i = 1; i <= m; i++) {
int val = updates[i].first;
int x = updates[i].second;
tree1.upd(l[x], r[x], val);
}
}
{ /// for cnt
for (int i = 1; i <= m; i++) {
int val = updates[i].first;
int x = updates[i].second;
tree2.upd(l[x], r[x], 1);
}
}
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:233:11: warning: unused variable 'val' [-Wunused-variable]
233 | int val = updates[i].first;
| ^~~
currencies.cpp:252:9: warning: unused variable 'z' [-Wunused-variable]
252 | int z = lca(s, t);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
89688 KB |
Output is correct |
| 2 |
Correct |
16 ms |
89692 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
89724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
89692 KB |
Output is correct |
| 2 |
Incorrect |
34 ms |
90228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
89692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
89688 KB |
Output is correct |
| 2 |
Correct |
16 ms |
89692 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
89724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
