#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100'001;
const int MAXK = 20;
struct Node {
Node *l, *r;
ll sum = 0;
int cnt = 0;
Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
Node(Node *a, Node *b) : l(a), r(b) {
if (a) {
sum += a->sum;
cnt += a->cnt;
}
if (b) {
sum += b->sum;
cnt += b->cnt;
}
}
};
Node *build(int tl, int tr) {
if (tl == tr) {
return new Node(0, 0);
} else {
int tm = (tl + tr) / 2;
return new Node(build(tl, tm), build(tm+1, tr));
}
}
Node *upd(Node *v, int tl, int tr, int pos, ll val, ll cnt) {
if (tl == tr) {
return new Node(v->sum + val, v->cnt + cnt);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
return new Node(upd(v->l, tl, tm, pos, val, cnt), v->r);
} else {
return new Node(v->l, upd(v->r, tm+1, tr, pos, val, cnt));
}
}
}
ll qry(Node *u, Node *v, Node *lca, int tl, int tr, ll silver) {
if (tl == tr) {
ll val = u->sum + v->sum - 2 * lca->sum;
ll golds = u->cnt + v->cnt - 2 * lca->cnt;
ll base = golds ? val / golds : 0;
ll bought = base ? silver / base : 0;
return max(0ll, golds - bought);
} else {
int tm = (tl + tr) / 2;
ll val = u->l->sum + v->l->sum - 2 * lca->l->sum;
if (val <= silver) {
return qry(u->r, v->r, lca->r, tm+1, tr, silver - val);
} else {
ll golds = u->r->cnt + v->r->cnt - 2 * lca->r->cnt;
return golds + qry(u->l, v->l, lca->l, tl, tm, silver);
}
}
}
vector<int> g[MAXN];
int up[MAXN][MAXK], tin[MAXN], tout[MAXN], n, m, q, timer = 1;
Node *root[MAXN];
ll cost[MAXN], checkpoints[MAXN];
void dfs(int u, int p = -1) {
tin[u] = timer++;
for (int v : g[u]) {
if (v != p) {
up[v][0] = u;
dfs(v, u);
}
}
tout[u] = timer++;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
for (int k = MAXK-1; k >= 0; k--) {
if (up[u][k] && !is_ancestor(up[u][k], v)) {
u = up[u][k];
}
}
return up[u][0];
}
void prelift() {
dfs(1);
for (int k = 1; k < MAXK; k++) {
for (int i = 1; i <= n; i++) {
up[i][k] = up[up[i][k-1]][k-1];
}
}
}
void dfs2(const vector<int> &comp, int u, int p = -1) {
if (p == -1) {
root[u] = build(1, n);
} else if (cost[u]) {
int pos = lower_bound(comp.begin(), comp.end(), cost[u])-comp.begin();
root[u] = upd(root[up[u][0]], 1, n, pos, cost[u], checkpoints[u]);
} else {
root[u] = root[up[u][0]];
}
for (int v : g[u]) {
if (v != p) dfs2(comp, v, u);
}
}
void build_tree() {
vector<int> comp = {0};
for (int i = 1; i <= n; i++) {
comp.emplace_back(cost[i]);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
g[0].emplace_back(1);
dfs2(comp, 0);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> q;
vector<pair<int, int>> edges;
for (int i = 1; i <= n-1; i++) {
int u, v; cin >> u >> v;
edges.emplace_back(u, v);
g[u].emplace_back(v);
g[v].emplace_back(u);
}
prelift();
for (int i = 1; i <= m; i++) {
int p, c; cin >> p >> c;
auto [u, v] = edges[p-1];
if (tin[u] > tin[v]) swap(u, v);
cost[v] += c;
checkpoints[v]++;
}
build_tree();
while (q--) {
ll s, t, x, y; cin >> s >> t >> x >> y;
int v = lca(s, t);
cout << max(-1ll, x-qry(root[s], root[t], root[v], 1, n, y)) << "\n";
}
return 0;
}
Compilation message
currencies.cpp: In constructor 'Node::Node(ll, int)':
currencies.cpp:12:9: warning: 'Node::cnt' will be initialized after [-Wreorder]
12 | int cnt = 0;
| ^~~
currencies.cpp:10:11: warning: 'Node* Node::l' [-Wreorder]
10 | Node *l, *r;
| ^
currencies.cpp:14:5: warning: when initialized here [-Wreorder]
14 | Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
| ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:148:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
148 | auto [u, v] = edges[p-1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
