#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int LOG = 17;
const int N = 1e5 + 5;
int n, m, q;
vector<int> g[N];
pair<int, int> edge[N];
pair<int, int> checkPoint[N];
int cnt;
int dep[N];
int up[LOG][N];
int in[N], out[N];
void dfs(int v, int p) {
in[v] = ++cnt;
for (int u : g[v]) {
if (u == p) {
continue;
}
dep[u] = dep[v] + 1;
up[0][u] = v;
for (int j = 1; j < LOG; ++j) {
up[j][u] = up[j - 1][up[j - 1][u]];
}
dfs(u, v);
}
out[v] = cnt;
}
struct Query {
int u, v, gold;
long long silver;
int l, r, m, ind, ans;
};
struct BIT {
int n;
vector<long long> tr;
BIT(int n_) : n(n_) {
tr.resize(n + 1);
}
void upd(int p, int v) {
while (p <= n) {
tr[p] += v;
p += p & -p;
}
}
void upd(int l, int r, int v) {
upd(l, v); upd(r + 1, -v);
}
long long qry(int p) {
long long ret = 0;
while (p) {
ret += tr[p];
p -= p & -p;
}
return ret;
}
};
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int j = 0; j < LOG; ++j) {
if ((dep[u] - dep[v]) >> j & 1) {
u = up[j][u];
}
}
if (u == v) return v;
for (int j = LOG - 1; j >= 0; --j) {
if (up[j][u] != up[j][v]) {
u = up[j][u]; v = up[j][v];
}
}
return up[0][u];
}
Query qs[N];
void solve() {
dfs(1, 1);
for (int i = 1; i <= q; ++i) {
qs[i].l = 0, qs[i].r = m, qs[i].ind = i;
}
for (int i = 1; i < n; ++i) {
if (dep[edge[i].first] > dep[edge[i].second]) {
swap(edge[i].first, edge[i].second);
}
}
sort(checkPoint + 1, checkPoint + 1 + m, [&](pair<int, int>& i, pair<int, int>& j) {
return i.second < j.second;
});
for (int iter = 0; iter < 20; ++iter) {
for (int i = 1; i <= q; ++i) {
qs[i].m = (qs[i].l + qs[i].r + 1) / 2;
}
sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
return i.m < j.m;
});
BIT sum(n);
int ptr = 1;
for (int i = 1; i <= q; ++i) {
while (ptr <= qs[i].m) {
int v = edge[checkPoint[ptr].first].second;
sum.upd(in[v], out[v], checkPoint[ptr].second);
ptr++;
}
long long t = sum.qry(in[qs[i].v]);
t += sum.qry(in[qs[i].u]);
t -= 2 * sum.qry(in[lca(qs[i].u, qs[i].v)]);
if (t <= qs[i].silver) {
qs[i].l = qs[i].m;
} else {
qs[i].r = qs[i].m - 1;
}
}
}
sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
return i.l < j.l;
});
BIT ones(n);
for (int i = 1; i <= m; ++i) {
int v = edge[checkPoint[i].first].second;
ones.upd(in[v], out[v], 1);
}
int ptr = 1;
for (int i = 1; i <= q; ++i) {
assert(qs[i].l == qs[i].r);
while (ptr <= qs[i].l) {
int v = edge[checkPoint[ptr].first].second;
ones.upd(in[v], out[v], -1);
ptr++;
}
int t = ones.qry(in[qs[i].v]);
t += ones.qry(in[qs[i].u]);
t -= 2 * ones.qry(in[lca(qs[i].u, qs[i].v)]);
qs[i].ans = qs[i].gold - t;
}
sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
return i.ind < j.ind;
});
for (int i = 1; i <= q; ++i) {
cout << max(-1, qs[i].ans) << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
edge[i] = {u, v};
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= m; ++i) {
cin >> checkPoint[i].first >> checkPoint[i].second;//Edge index, Cj silver
}
for (int i = 1; i <= q; ++i) {
cin >> qs[i].u >> qs[i].v >> qs[i].gold >> qs[i].silver;
qs[i].ind = i;
}
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10584 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
8 ms |
10584 KB |
Output is correct |
6 |
Correct |
12 ms |
11096 KB |
Output is correct |
7 |
Correct |
10 ms |
10836 KB |
Output is correct |
8 |
Correct |
11 ms |
10844 KB |
Output is correct |
9 |
Correct |
14 ms |
10896 KB |
Output is correct |
10 |
Correct |
14 ms |
10844 KB |
Output is correct |
11 |
Correct |
10 ms |
10740 KB |
Output is correct |
12 |
Correct |
11 ms |
10840 KB |
Output is correct |
13 |
Correct |
11 ms |
10844 KB |
Output is correct |
14 |
Correct |
15 ms |
11004 KB |
Output is correct |
15 |
Correct |
14 ms |
10716 KB |
Output is correct |
16 |
Correct |
14 ms |
10948 KB |
Output is correct |
17 |
Correct |
13 ms |
10904 KB |
Output is correct |
18 |
Correct |
13 ms |
10844 KB |
Output is correct |
19 |
Correct |
10 ms |
10712 KB |
Output is correct |
20 |
Correct |
8 ms |
11148 KB |
Output is correct |
21 |
Correct |
10 ms |
10844 KB |
Output is correct |
22 |
Correct |
11 ms |
10844 KB |
Output is correct |
23 |
Correct |
10 ms |
10844 KB |
Output is correct |
24 |
Correct |
10 ms |
10844 KB |
Output is correct |
25 |
Correct |
10 ms |
10900 KB |
Output is correct |
26 |
Correct |
9 ms |
10840 KB |
Output is correct |
27 |
Correct |
7 ms |
10844 KB |
Output is correct |
28 |
Correct |
8 ms |
10840 KB |
Output is correct |
29 |
Correct |
7 ms |
10844 KB |
Output is correct |
30 |
Correct |
15 ms |
10860 KB |
Output is correct |
31 |
Correct |
10 ms |
10840 KB |
Output is correct |
32 |
Correct |
12 ms |
10896 KB |
Output is correct |
33 |
Correct |
11 ms |
10840 KB |
Output is correct |
34 |
Correct |
11 ms |
11104 KB |
Output is correct |
35 |
Correct |
11 ms |
11052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
Output is correct |
2 |
Correct |
13 ms |
10812 KB |
Output is correct |
3 |
Correct |
10 ms |
10892 KB |
Output is correct |
4 |
Correct |
10 ms |
10840 KB |
Output is correct |
5 |
Correct |
617 ms |
25448 KB |
Output is correct |
6 |
Correct |
641 ms |
24124 KB |
Output is correct |
7 |
Correct |
620 ms |
24668 KB |
Output is correct |
8 |
Correct |
534 ms |
24576 KB |
Output is correct |
9 |
Correct |
516 ms |
24172 KB |
Output is correct |
10 |
Correct |
865 ms |
26308 KB |
Output is correct |
11 |
Correct |
827 ms |
26336 KB |
Output is correct |
12 |
Correct |
879 ms |
26336 KB |
Output is correct |
13 |
Correct |
877 ms |
26324 KB |
Output is correct |
14 |
Correct |
756 ms |
26320 KB |
Output is correct |
15 |
Correct |
1247 ms |
33992 KB |
Output is correct |
16 |
Correct |
1103 ms |
34472 KB |
Output is correct |
17 |
Correct |
1221 ms |
33584 KB |
Output is correct |
18 |
Correct |
1225 ms |
26652 KB |
Output is correct |
19 |
Correct |
1137 ms |
26716 KB |
Output is correct |
20 |
Correct |
1215 ms |
26744 KB |
Output is correct |
21 |
Correct |
539 ms |
25740 KB |
Output is correct |
22 |
Correct |
704 ms |
25912 KB |
Output is correct |
23 |
Correct |
574 ms |
26076 KB |
Output is correct |
24 |
Correct |
606 ms |
26132 KB |
Output is correct |
25 |
Correct |
630 ms |
26620 KB |
Output is correct |
26 |
Correct |
672 ms |
26636 KB |
Output is correct |
27 |
Correct |
556 ms |
26620 KB |
Output is correct |
28 |
Correct |
437 ms |
26144 KB |
Output is correct |
29 |
Correct |
379 ms |
25964 KB |
Output is correct |
30 |
Correct |
466 ms |
26388 KB |
Output is correct |
31 |
Correct |
438 ms |
26376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10592 KB |
Output is correct |
2 |
Correct |
11 ms |
10840 KB |
Output is correct |
3 |
Correct |
12 ms |
10844 KB |
Output is correct |
4 |
Correct |
11 ms |
10840 KB |
Output is correct |
5 |
Correct |
634 ms |
32520 KB |
Output is correct |
6 |
Correct |
676 ms |
31988 KB |
Output is correct |
7 |
Correct |
719 ms |
27720 KB |
Output is correct |
8 |
Correct |
1087 ms |
34604 KB |
Output is correct |
9 |
Correct |
990 ms |
34600 KB |
Output is correct |
10 |
Correct |
984 ms |
34604 KB |
Output is correct |
11 |
Correct |
686 ms |
34624 KB |
Output is correct |
12 |
Correct |
670 ms |
34628 KB |
Output is correct |
13 |
Correct |
681 ms |
34624 KB |
Output is correct |
14 |
Correct |
314 ms |
34516 KB |
Output is correct |
15 |
Correct |
331 ms |
34480 KB |
Output is correct |
16 |
Correct |
447 ms |
34840 KB |
Output is correct |
17 |
Correct |
483 ms |
34596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10584 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
8 ms |
10584 KB |
Output is correct |
6 |
Correct |
12 ms |
11096 KB |
Output is correct |
7 |
Correct |
10 ms |
10836 KB |
Output is correct |
8 |
Correct |
11 ms |
10844 KB |
Output is correct |
9 |
Correct |
14 ms |
10896 KB |
Output is correct |
10 |
Correct |
14 ms |
10844 KB |
Output is correct |
11 |
Correct |
10 ms |
10740 KB |
Output is correct |
12 |
Correct |
11 ms |
10840 KB |
Output is correct |
13 |
Correct |
11 ms |
10844 KB |
Output is correct |
14 |
Correct |
15 ms |
11004 KB |
Output is correct |
15 |
Correct |
14 ms |
10716 KB |
Output is correct |
16 |
Correct |
14 ms |
10948 KB |
Output is correct |
17 |
Correct |
13 ms |
10904 KB |
Output is correct |
18 |
Correct |
13 ms |
10844 KB |
Output is correct |
19 |
Correct |
10 ms |
10712 KB |
Output is correct |
20 |
Correct |
8 ms |
11148 KB |
Output is correct |
21 |
Correct |
10 ms |
10844 KB |
Output is correct |
22 |
Correct |
11 ms |
10844 KB |
Output is correct |
23 |
Correct |
10 ms |
10844 KB |
Output is correct |
24 |
Correct |
10 ms |
10844 KB |
Output is correct |
25 |
Correct |
10 ms |
10900 KB |
Output is correct |
26 |
Correct |
9 ms |
10840 KB |
Output is correct |
27 |
Correct |
7 ms |
10844 KB |
Output is correct |
28 |
Correct |
8 ms |
10840 KB |
Output is correct |
29 |
Correct |
7 ms |
10844 KB |
Output is correct |
30 |
Correct |
15 ms |
10860 KB |
Output is correct |
31 |
Correct |
10 ms |
10840 KB |
Output is correct |
32 |
Correct |
12 ms |
10896 KB |
Output is correct |
33 |
Correct |
11 ms |
10840 KB |
Output is correct |
34 |
Correct |
11 ms |
11104 KB |
Output is correct |
35 |
Correct |
11 ms |
11052 KB |
Output is correct |
36 |
Correct |
3 ms |
10584 KB |
Output is correct |
37 |
Correct |
13 ms |
10812 KB |
Output is correct |
38 |
Correct |
10 ms |
10892 KB |
Output is correct |
39 |
Correct |
10 ms |
10840 KB |
Output is correct |
40 |
Correct |
617 ms |
25448 KB |
Output is correct |
41 |
Correct |
641 ms |
24124 KB |
Output is correct |
42 |
Correct |
620 ms |
24668 KB |
Output is correct |
43 |
Correct |
534 ms |
24576 KB |
Output is correct |
44 |
Correct |
516 ms |
24172 KB |
Output is correct |
45 |
Correct |
865 ms |
26308 KB |
Output is correct |
46 |
Correct |
827 ms |
26336 KB |
Output is correct |
47 |
Correct |
879 ms |
26336 KB |
Output is correct |
48 |
Correct |
877 ms |
26324 KB |
Output is correct |
49 |
Correct |
756 ms |
26320 KB |
Output is correct |
50 |
Correct |
1247 ms |
33992 KB |
Output is correct |
51 |
Correct |
1103 ms |
34472 KB |
Output is correct |
52 |
Correct |
1221 ms |
33584 KB |
Output is correct |
53 |
Correct |
1225 ms |
26652 KB |
Output is correct |
54 |
Correct |
1137 ms |
26716 KB |
Output is correct |
55 |
Correct |
1215 ms |
26744 KB |
Output is correct |
56 |
Correct |
539 ms |
25740 KB |
Output is correct |
57 |
Correct |
704 ms |
25912 KB |
Output is correct |
58 |
Correct |
574 ms |
26076 KB |
Output is correct |
59 |
Correct |
606 ms |
26132 KB |
Output is correct |
60 |
Correct |
630 ms |
26620 KB |
Output is correct |
61 |
Correct |
672 ms |
26636 KB |
Output is correct |
62 |
Correct |
556 ms |
26620 KB |
Output is correct |
63 |
Correct |
437 ms |
26144 KB |
Output is correct |
64 |
Correct |
379 ms |
25964 KB |
Output is correct |
65 |
Correct |
466 ms |
26388 KB |
Output is correct |
66 |
Correct |
438 ms |
26376 KB |
Output is correct |
67 |
Correct |
3 ms |
10592 KB |
Output is correct |
68 |
Correct |
11 ms |
10840 KB |
Output is correct |
69 |
Correct |
12 ms |
10844 KB |
Output is correct |
70 |
Correct |
11 ms |
10840 KB |
Output is correct |
71 |
Correct |
634 ms |
32520 KB |
Output is correct |
72 |
Correct |
676 ms |
31988 KB |
Output is correct |
73 |
Correct |
719 ms |
27720 KB |
Output is correct |
74 |
Correct |
1087 ms |
34604 KB |
Output is correct |
75 |
Correct |
990 ms |
34600 KB |
Output is correct |
76 |
Correct |
984 ms |
34604 KB |
Output is correct |
77 |
Correct |
686 ms |
34624 KB |
Output is correct |
78 |
Correct |
670 ms |
34628 KB |
Output is correct |
79 |
Correct |
681 ms |
34624 KB |
Output is correct |
80 |
Correct |
314 ms |
34516 KB |
Output is correct |
81 |
Correct |
331 ms |
34480 KB |
Output is correct |
82 |
Correct |
447 ms |
34840 KB |
Output is correct |
83 |
Correct |
483 ms |
34596 KB |
Output is correct |
84 |
Correct |
497 ms |
24412 KB |
Output is correct |
85 |
Correct |
531 ms |
22688 KB |
Output is correct |
86 |
Correct |
489 ms |
22032 KB |
Output is correct |
87 |
Correct |
833 ms |
26260 KB |
Output is correct |
88 |
Correct |
933 ms |
26268 KB |
Output is correct |
89 |
Correct |
828 ms |
26264 KB |
Output is correct |
90 |
Correct |
885 ms |
26260 KB |
Output is correct |
91 |
Correct |
833 ms |
26476 KB |
Output is correct |
92 |
Correct |
1431 ms |
31796 KB |
Output is correct |
93 |
Correct |
1277 ms |
33320 KB |
Output is correct |
94 |
Correct |
1203 ms |
26680 KB |
Output is correct |
95 |
Correct |
1307 ms |
26712 KB |
Output is correct |
96 |
Correct |
1099 ms |
26724 KB |
Output is correct |
97 |
Correct |
1247 ms |
26664 KB |
Output is correct |
98 |
Correct |
601 ms |
26088 KB |
Output is correct |
99 |
Correct |
582 ms |
25860 KB |
Output is correct |
100 |
Correct |
719 ms |
26044 KB |
Output is correct |
101 |
Correct |
607 ms |
25884 KB |
Output is correct |
102 |
Correct |
726 ms |
26584 KB |
Output is correct |
103 |
Correct |
647 ms |
26668 KB |
Output is correct |
104 |
Correct |
670 ms |
26552 KB |
Output is correct |
105 |
Correct |
413 ms |
26124 KB |
Output is correct |
106 |
Correct |
391 ms |
26304 KB |
Output is correct |
107 |
Correct |
480 ms |
26228 KB |
Output is correct |
108 |
Correct |
460 ms |
26224 KB |
Output is correct |