#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 100000 + 7;
const int K = 20;
const int B = 317;
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];
ll sumToRoot[B][N];
ll prefSum[B][N];
int countToRoot[B][N];
int prefCount[B][N];
int get_bucket(int x) {
return (x - 1) / B + 1;
}
struct segtree {
int n;
vector<ll> tree;
vector<ll> lazy;
void init(int nn) {
n = nn;
tree.resize(4 * n + 1);
lazy.resize(4 * n + 1);
for (int i = 1; i <= 4 * n; i++) {
tree[i] = 0;
lazy[i] = 0;
}
}
void push(int v, int tl, int tr) {
if (tl < tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
tree[v] += lazy[v];
lazy[v] = 0;
}
void applyRange(int v, int tl, int tr, int x, int y, ll val) {
push(v, tl, tr);
if (x <= tl && tr <= y) {
lazy[v] += val;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (x <= tm) {
applyRange(2 * v, tl, tm, x, min(tm, y), val);
}
if (tm + 1 <= y) {
applyRange(2 * v + 1, tm + 1, tr, max(x, tm + 1), y, val);
}
push(2 * v, tl, tm);
push(2 * v + 1, tm + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
ll force(int v, int tl, int tr, int x, int y) {
push(v, tl, tr);
if (x <= tl && tr <= y) {
return tree[v];
}
int tm = (tl + tr) / 2;
if (x <= tm && y <= tm) {
return force(2 * v, tl, tm, x, y);
} else if (tm + 1 <= x && tm + 1 <= y) {
return force(2 * v + 1, tm + 1, tr, x, y);
} else {
return force(2 * v, tl, tm, x, tm) + force(2 * v + 1, tm + 1, tr, tm + 1, tr);
}
}
};
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) {
return l[x] <= l[y] && r[y] <= r[x];
}
ll getToRoot(int when, int node) {
if (node == 0) {
return 0;
}
int bucket = get_bucket(when) - 1;
ll sol = prefSum[bucket][node];
for (int i = B * bucket + 1; i <= when; i++) {
ll val = updates[i].first;
int x = updates[i].second;
if (is_ancestor(x, node)) {
sol += val;
}
}
return sol;
}
ll get_sum(int when, int x, int y) {
int z = lca(x, y);
return getToRoot(when, x) + getToRoot(when, y) - 2 * getToRoot(when, z);
}
ll getToRoot2(int when, int node) {
if (node == 0) {
return 0;
}
int bucket = get_bucket(when) - 1;
ll sol = prefCount[bucket][node];
for (int i = B * bucket + 1; i <= when; i++) {
int x = updates[i].second;
if (is_ancestor(x, node)) {
sol++;
}
}
return sol;
}
ll get_count(int when, int x, int y) {
int z = lca(x, y);
return getToRoot2(when, x) + getToRoot2(when, y) - 2 * getToRoot2(when, z);
}
struct T {
int s;
int t;
int x;
ll y;
int low;
int high;
int mid;
int sol;
int id;
};
vector<T> queries;
int print[N];
void get_moments() {
int mm = m;
while (m > 0) {
m /= 2;
int k = 0;
vector<T> new_queries, others;
while (k < (int) queries.size()) {
int now = get_sum(queries[k].mid, queries[k].s, queries[k].t);
if (now <= queries[k].y) {
queries[k].sol = queries[k].mid;
queries[k].low = queries[k].mid;
queries[k].mid = (queries[k].low + queries[k].high) / 2;
others.push_back(queries[k]);
} else {
queries[k].high = queries[k].mid + 1;
queries[k].mid = (queries[k].low + queries[k].high) / 2;
new_queries.push_back(queries[k]);
}
k++;
}
for (auto &it : others) {
new_queries.push_back(it);
}
others.clear();
queries = new_queries;
}
m = mm;
}
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
for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
segtree tree;
tree.init(n);
for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
ll val = updates[i].first;
int x = updates[i].second;
if (x != 0) {
tree.applyRange(1, 1, n, l[x], r[x], val);
}
}
for (int i = 1; i <= n; i++) {
sumToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
}
}
for (int i = 1; i <= n; i++) {
for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
prefSum[bucket][i] = prefSum[bucket - 1][i] + sumToRoot[bucket][i];
}
}
}
{ /// for cnt
for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
segtree tree;
tree.init(n);
for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
int x = updates[i].second;
if (x != 0) {
tree.applyRange(1, 1, n, l[x], r[x], 1);
}
}
for (int i = 1; i <= n; i++) {
countToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
}
}
for (int i = 1; i <= n; i++) {
for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
prefCount[bucket][i] = prefCount[bucket - 1][i] + countToRoot[bucket][i];
}
}
}
for (int i = 0; i < q; i++) {
T aux;
cin >> aux.s >> aux.t >> aux.x >> aux.y;
aux.low = 1;
aux.high = m;
aux.mid = (m + 1) / 2;
aux.sol = 0;
aux.id = i + 1;
queries.push_back(aux);
}
get_moments();
for (int iq = 0; iq < q; iq++) {
int s = queries[iq].s;
int t = queries[iq].t;
int x = queries[iq].x;
ll y = queries[iq].y;
int sol = queries[iq].sol;
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;
}
print[queries[iq].id] = keep;
}
for (int i = 1; i <= q; i++) {
cout << print[i] << "\n";
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:300:8: warning: unused variable 'y' [-Wunused-variable]
300 | ll y = queries[iq].y;
| ^
currencies.cpp:303:9: warning: unused variable 'z' [-Wunused-variable]
303 | int z = lca(s, t);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
28764 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
28764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
28892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
28760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
28764 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
28764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
