#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 100087, mod = 998244353, M = N * 40, logN = 19;
vector <int> vec;
struct Seg {
static Seg mem[M], *pt;
int l, r, m, cnt;
ll sum;
Seg* ch[2];
Seg () = default;
Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
if (r - l > 1) {
ch[0] = new (pt++) Seg(l, m);
ch[1] = new (pt++) Seg(m, r);
}
}
Seg (Seg *i) : l(i->l), r(i->r), m(i->m), sum(i->sum), cnt(i->cnt), ch{i->ch[0], i->ch[1]} {}
void pull() {sum = ch[0]->sum + ch[1]->sum, cnt = ch[0]->cnt + ch[1]->cnt;}
Seg* modify(int p) {
Seg *now = new (pt++) Seg(*this);
if (r - l == 1) {
now->sum += vec[l];
now->cnt += 1;
} else {
now->ch[p >= m] = ch[p >= m]->modify(p);
now->pull();
}
return now;
}
} Seg::mem[M], *Seg::pt = mem;
vector <pii> adj[N];
vector <int> cost[N];
int jump[N][logN], in[N], out[N], _t;
Seg* val[N];
void dfs(int v, int pa) {
in[v] = _t++, jump[v][0] = pa;
for (int j = 1; j < logN; ++j) {
int k = jump[v][j - 1];
jump[v][j] = ~k ? jump[k][j - 1] : -1;
}
for (auto [u, eid] : adj[v]) if (u != pa) {
val[u] = new (Seg::pt++) Seg(val[v]);
for (int w : cost[eid]) {
int id = lower_bound(all(vec), w) - vec.begin();
val[u] = val[u]->modify(id);
}
dfs(u, v);
}
out[v] = _t++;
}
int anc(int u, int v) {
return in[u] <= in[v] && out[u] >= out[v];
}
int lca(int u, int v) {
if (anc(u, v)) {
return u;
}
if (anc(v, u)) {
return v;
}
for (int i = logN - 1; ~i; --i) {
if (~jump[u][i] && !anc(jump[u][i], v)) {
u = jump[u][i];
}
}
return jump[u][0];
}
int query(int u, int v, ll tot) {
int l = lca(u, v);
Seg *tl = val[u], *tr = val[v], *tm = val[l];
int ans = 0;
while (tl->r - tl->l > 1) {
ll left = tl->ch[0]->sum + tr->ch[0]->sum - 2 * tm->ch[0]->sum;
if (left <= tot) {
tl = tl->ch[1];
tr = tr->ch[1];
tm = tm->ch[1];
tot -= left;
} else {
ans += tl->ch[1]->cnt + tr->ch[1]->cnt - 2 * tm->ch[1]->cnt;
tl = tl->ch[0];
tr = tr->ch[0];
tm = tm->ch[0];
}
}
int tmp = tl->cnt + tr->cnt - 2 * tm->cnt;
ans += tmp - min(tot / vec[tl->l], 1ll * tmp);
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 0, u, v; i < n - 1; ++i) {
cin >> u >> v, --u, --v;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
for (int i = 0, u, v; i < m; ++i) {
cin >> u >> v, --u;
cost[u].pb(v);
vec.pb(v);
}
sort(all(vec)), vec.resize(unique(all(vec)) - vec.begin());
val[0] = new (Seg::pt++) Seg(0, int(vec.size()));
dfs(0, -1);
while (q--) {
int u, v, x; ll y;
cin >> u >> v >> x >> y, --u, --v;
int tmp = query(u, v, y);
cout << max(x - tmp, -1) << '\n';
}
}
/*
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
*/
Compilation message
currencies.cpp: In constructor 'Seg::Seg(int, int)':
currencies.cpp:17:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
| ~~^~~
currencies.cpp:14:8: warning: 'Seg::sum' will be initialized after [-Wreorder]
14 | ll sum;
| ^~~
currencies.cpp:13:18: warning: 'int Seg::cnt' [-Wreorder]
13 | int l, r, m, cnt;
| ^~~
currencies.cpp:17:5: warning: when initialized here [-Wreorder]
17 | Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), sum(0), cnt(0) {
| ^~~
currencies.cpp: In constructor 'Seg::Seg(Seg*)':
currencies.cpp:14:8: warning: 'Seg::sum' will be initialized after [-Wreorder]
14 | ll sum;
| ^~~
currencies.cpp:13:18: warning: 'int Seg::cnt' [-Wreorder]
13 | int l, r, m, cnt;
| ^~~
currencies.cpp:23:5: warning: when initialized here [-Wreorder]
23 | Seg (Seg *i) : l(i->l), r(i->r), m(i->m), sum(i->sum), cnt(i->cnt), ch{i->ch[0], i->ch[1]} {}
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
3 ms |
9040 KB |
Output is correct |
6 |
Correct |
4 ms |
9052 KB |
Output is correct |
7 |
Correct |
3 ms |
6748 KB |
Output is correct |
8 |
Correct |
4 ms |
9052 KB |
Output is correct |
9 |
Correct |
4 ms |
9052 KB |
Output is correct |
10 |
Correct |
5 ms |
8936 KB |
Output is correct |
11 |
Correct |
4 ms |
9052 KB |
Output is correct |
12 |
Correct |
4 ms |
9052 KB |
Output is correct |
13 |
Correct |
5 ms |
9404 KB |
Output is correct |
14 |
Correct |
4 ms |
9308 KB |
Output is correct |
15 |
Correct |
4 ms |
9048 KB |
Output is correct |
16 |
Correct |
4 ms |
9052 KB |
Output is correct |
17 |
Correct |
4 ms |
9052 KB |
Output is correct |
18 |
Correct |
4 ms |
9048 KB |
Output is correct |
19 |
Correct |
4 ms |
9052 KB |
Output is correct |
20 |
Correct |
4 ms |
9048 KB |
Output is correct |
21 |
Correct |
4 ms |
9052 KB |
Output is correct |
22 |
Correct |
4 ms |
9052 KB |
Output is correct |
23 |
Correct |
4 ms |
9052 KB |
Output is correct |
24 |
Correct |
4 ms |
9052 KB |
Output is correct |
25 |
Correct |
4 ms |
8940 KB |
Output is correct |
26 |
Correct |
4 ms |
8944 KB |
Output is correct |
27 |
Correct |
4 ms |
9188 KB |
Output is correct |
28 |
Correct |
4 ms |
9052 KB |
Output is correct |
29 |
Correct |
4 ms |
9052 KB |
Output is correct |
30 |
Correct |
3 ms |
7004 KB |
Output is correct |
31 |
Correct |
3 ms |
7004 KB |
Output is correct |
32 |
Correct |
3 ms |
7004 KB |
Output is correct |
33 |
Correct |
5 ms |
9308 KB |
Output is correct |
34 |
Correct |
5 ms |
9308 KB |
Output is correct |
35 |
Correct |
5 ms |
9276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
7004 KB |
Output is correct |
3 |
Correct |
3 ms |
7000 KB |
Output is correct |
4 |
Correct |
3 ms |
7004 KB |
Output is correct |
5 |
Correct |
123 ms |
33704 KB |
Output is correct |
6 |
Correct |
104 ms |
30152 KB |
Output is correct |
7 |
Correct |
110 ms |
30672 KB |
Output is correct |
8 |
Correct |
94 ms |
30060 KB |
Output is correct |
9 |
Correct |
103 ms |
30160 KB |
Output is correct |
10 |
Correct |
142 ms |
34764 KB |
Output is correct |
11 |
Correct |
131 ms |
34764 KB |
Output is correct |
12 |
Correct |
127 ms |
34764 KB |
Output is correct |
13 |
Correct |
124 ms |
34760 KB |
Output is correct |
14 |
Correct |
144 ms |
34560 KB |
Output is correct |
15 |
Correct |
166 ms |
53504 KB |
Output is correct |
16 |
Correct |
166 ms |
54660 KB |
Output is correct |
17 |
Correct |
156 ms |
52432 KB |
Output is correct |
18 |
Correct |
151 ms |
35020 KB |
Output is correct |
19 |
Correct |
151 ms |
34900 KB |
Output is correct |
20 |
Correct |
146 ms |
35004 KB |
Output is correct |
21 |
Correct |
121 ms |
34084 KB |
Output is correct |
22 |
Correct |
128 ms |
34676 KB |
Output is correct |
23 |
Correct |
110 ms |
34244 KB |
Output is correct |
24 |
Correct |
116 ms |
34212 KB |
Output is correct |
25 |
Correct |
140 ms |
34592 KB |
Output is correct |
26 |
Correct |
127 ms |
34500 KB |
Output is correct |
27 |
Correct |
121 ms |
34496 KB |
Output is correct |
28 |
Correct |
126 ms |
34368 KB |
Output is correct |
29 |
Correct |
112 ms |
34504 KB |
Output is correct |
30 |
Correct |
119 ms |
34808 KB |
Output is correct |
31 |
Correct |
113 ms |
34808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6692 KB |
Output is correct |
2 |
Correct |
5 ms |
9304 KB |
Output is correct |
3 |
Correct |
4 ms |
9308 KB |
Output is correct |
4 |
Correct |
4 ms |
9308 KB |
Output is correct |
5 |
Correct |
236 ms |
95004 KB |
Output is correct |
6 |
Correct |
214 ms |
83780 KB |
Output is correct |
7 |
Correct |
305 ms |
106180 KB |
Output is correct |
8 |
Correct |
416 ms |
129172 KB |
Output is correct |
9 |
Correct |
410 ms |
129192 KB |
Output is correct |
10 |
Correct |
411 ms |
127128 KB |
Output is correct |
11 |
Correct |
352 ms |
128456 KB |
Output is correct |
12 |
Correct |
376 ms |
128644 KB |
Output is correct |
13 |
Correct |
356 ms |
128536 KB |
Output is correct |
14 |
Correct |
244 ms |
128828 KB |
Output is correct |
15 |
Correct |
254 ms |
128800 KB |
Output is correct |
16 |
Correct |
274 ms |
127108 KB |
Output is correct |
17 |
Correct |
292 ms |
127076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
3 ms |
9040 KB |
Output is correct |
6 |
Correct |
4 ms |
9052 KB |
Output is correct |
7 |
Correct |
3 ms |
6748 KB |
Output is correct |
8 |
Correct |
4 ms |
9052 KB |
Output is correct |
9 |
Correct |
4 ms |
9052 KB |
Output is correct |
10 |
Correct |
5 ms |
8936 KB |
Output is correct |
11 |
Correct |
4 ms |
9052 KB |
Output is correct |
12 |
Correct |
4 ms |
9052 KB |
Output is correct |
13 |
Correct |
5 ms |
9404 KB |
Output is correct |
14 |
Correct |
4 ms |
9308 KB |
Output is correct |
15 |
Correct |
4 ms |
9048 KB |
Output is correct |
16 |
Correct |
4 ms |
9052 KB |
Output is correct |
17 |
Correct |
4 ms |
9052 KB |
Output is correct |
18 |
Correct |
4 ms |
9048 KB |
Output is correct |
19 |
Correct |
4 ms |
9052 KB |
Output is correct |
20 |
Correct |
4 ms |
9048 KB |
Output is correct |
21 |
Correct |
4 ms |
9052 KB |
Output is correct |
22 |
Correct |
4 ms |
9052 KB |
Output is correct |
23 |
Correct |
4 ms |
9052 KB |
Output is correct |
24 |
Correct |
4 ms |
9052 KB |
Output is correct |
25 |
Correct |
4 ms |
8940 KB |
Output is correct |
26 |
Correct |
4 ms |
8944 KB |
Output is correct |
27 |
Correct |
4 ms |
9188 KB |
Output is correct |
28 |
Correct |
4 ms |
9052 KB |
Output is correct |
29 |
Correct |
4 ms |
9052 KB |
Output is correct |
30 |
Correct |
3 ms |
7004 KB |
Output is correct |
31 |
Correct |
3 ms |
7004 KB |
Output is correct |
32 |
Correct |
3 ms |
7004 KB |
Output is correct |
33 |
Correct |
5 ms |
9308 KB |
Output is correct |
34 |
Correct |
5 ms |
9308 KB |
Output is correct |
35 |
Correct |
5 ms |
9276 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
3 ms |
7004 KB |
Output is correct |
38 |
Correct |
3 ms |
7000 KB |
Output is correct |
39 |
Correct |
3 ms |
7004 KB |
Output is correct |
40 |
Correct |
123 ms |
33704 KB |
Output is correct |
41 |
Correct |
104 ms |
30152 KB |
Output is correct |
42 |
Correct |
110 ms |
30672 KB |
Output is correct |
43 |
Correct |
94 ms |
30060 KB |
Output is correct |
44 |
Correct |
103 ms |
30160 KB |
Output is correct |
45 |
Correct |
142 ms |
34764 KB |
Output is correct |
46 |
Correct |
131 ms |
34764 KB |
Output is correct |
47 |
Correct |
127 ms |
34764 KB |
Output is correct |
48 |
Correct |
124 ms |
34760 KB |
Output is correct |
49 |
Correct |
144 ms |
34560 KB |
Output is correct |
50 |
Correct |
166 ms |
53504 KB |
Output is correct |
51 |
Correct |
166 ms |
54660 KB |
Output is correct |
52 |
Correct |
156 ms |
52432 KB |
Output is correct |
53 |
Correct |
151 ms |
35020 KB |
Output is correct |
54 |
Correct |
151 ms |
34900 KB |
Output is correct |
55 |
Correct |
146 ms |
35004 KB |
Output is correct |
56 |
Correct |
121 ms |
34084 KB |
Output is correct |
57 |
Correct |
128 ms |
34676 KB |
Output is correct |
58 |
Correct |
110 ms |
34244 KB |
Output is correct |
59 |
Correct |
116 ms |
34212 KB |
Output is correct |
60 |
Correct |
140 ms |
34592 KB |
Output is correct |
61 |
Correct |
127 ms |
34500 KB |
Output is correct |
62 |
Correct |
121 ms |
34496 KB |
Output is correct |
63 |
Correct |
126 ms |
34368 KB |
Output is correct |
64 |
Correct |
112 ms |
34504 KB |
Output is correct |
65 |
Correct |
119 ms |
34808 KB |
Output is correct |
66 |
Correct |
113 ms |
34808 KB |
Output is correct |
67 |
Correct |
2 ms |
6692 KB |
Output is correct |
68 |
Correct |
5 ms |
9304 KB |
Output is correct |
69 |
Correct |
4 ms |
9308 KB |
Output is correct |
70 |
Correct |
4 ms |
9308 KB |
Output is correct |
71 |
Correct |
236 ms |
95004 KB |
Output is correct |
72 |
Correct |
214 ms |
83780 KB |
Output is correct |
73 |
Correct |
305 ms |
106180 KB |
Output is correct |
74 |
Correct |
416 ms |
129172 KB |
Output is correct |
75 |
Correct |
410 ms |
129192 KB |
Output is correct |
76 |
Correct |
411 ms |
127128 KB |
Output is correct |
77 |
Correct |
352 ms |
128456 KB |
Output is correct |
78 |
Correct |
376 ms |
128644 KB |
Output is correct |
79 |
Correct |
356 ms |
128536 KB |
Output is correct |
80 |
Correct |
244 ms |
128828 KB |
Output is correct |
81 |
Correct |
254 ms |
128800 KB |
Output is correct |
82 |
Correct |
274 ms |
127108 KB |
Output is correct |
83 |
Correct |
292 ms |
127076 KB |
Output is correct |
84 |
Correct |
256 ms |
100368 KB |
Output is correct |
85 |
Correct |
206 ms |
88084 KB |
Output is correct |
86 |
Correct |
160 ms |
64828 KB |
Output is correct |
87 |
Correct |
288 ms |
108372 KB |
Output is correct |
88 |
Correct |
308 ms |
108600 KB |
Output is correct |
89 |
Correct |
280 ms |
108344 KB |
Output is correct |
90 |
Correct |
300 ms |
106644 KB |
Output is correct |
91 |
Correct |
281 ms |
108328 KB |
Output is correct |
92 |
Correct |
510 ms |
119404 KB |
Output is correct |
93 |
Correct |
503 ms |
123768 KB |
Output is correct |
94 |
Correct |
444 ms |
106556 KB |
Output is correct |
95 |
Correct |
472 ms |
107020 KB |
Output is correct |
96 |
Correct |
450 ms |
106696 KB |
Output is correct |
97 |
Correct |
432 ms |
108740 KB |
Output is correct |
98 |
Correct |
259 ms |
108072 KB |
Output is correct |
99 |
Correct |
248 ms |
108196 KB |
Output is correct |
100 |
Correct |
254 ms |
108208 KB |
Output is correct |
101 |
Correct |
240 ms |
108232 KB |
Output is correct |
102 |
Correct |
282 ms |
108400 KB |
Output is correct |
103 |
Correct |
275 ms |
108412 KB |
Output is correct |
104 |
Correct |
285 ms |
108324 KB |
Output is correct |
105 |
Correct |
200 ms |
108632 KB |
Output is correct |
106 |
Correct |
204 ms |
108488 KB |
Output is correct |
107 |
Correct |
208 ms |
108456 KB |
Output is correct |
108 |
Correct |
208 ms |
108452 KB |
Output is correct |