#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
const int MX = 1e5 + 5;
const int mod = 998244353;
int n, m, q;
int a[MX], b[MX];
int p[MX], c[MX];
int s[MX], t[MX], x[MX];
ll y[MX];
int l[MX], r[MX], mid[MX], ans[MX];
int pos[MX], sz[MX], d[MX];
int hld_pa[MX], pa[MX];
ll tree[4 * MX];
int nm[4 * MX];
int cnt, num;
vector<int> adj[MX], h[MX];
vector<pair<int, int>> cst;
void dfs(int u, int pre) {
pa[u] = pre;
sz[u] = 1;
int mx = 0;
for(int i = 0; i < (int)adj[u].size(); i++) {
if(adj[u][i] == pre) continue;
d[adj[u][i]] = d[u] + 1;
dfs(adj[u][i], u);
mx = max(mx, sz[adj[u][i]]);
sz[u] += sz[adj[u][i]];
}
for(int i = 0; i < (int)adj[u].size(); i++) {
if(adj[u][i] == pre) continue;
if(sz[adj[u][i]] == mx) {
swap(adj[u][i], adj[u][0]);
break;
}
}
}
void hld(int u) {
pos[u] = num;
num++;
for(int i = 0; i < (int)adj[u].size(); i++) {
if(d[adj[u][i]] < d[u]) continue;
if(!i) hld_pa[adj[u][i]] = hld_pa[u];
else hld_pa[adj[u][i]] = adj[u][i];
}
for(int i = 0; i < (int)adj[u].size(); i++) {
if(d[adj[u][i]] < d[u]) continue;
hld(adj[u][i]);
}
}
void update(int id, int l, int r, int pos, int x) {
tree[id] += x;
nm[id]++;
if(l == r) return;
int mid = (l + r) / 2;
if(mid < pos) update(id * 2 + 2, mid + 1, r, pos, x);
else update(id * 2 + 1, l, mid, pos, x);
}
ll query(int id, int l, int r, int L, int R) {
if(L > r || l > R) return 0;
if(L <= l && r <= R) return tree[id];
int mid = (l + r) / 2;
return query(id * 2 + 1, l, mid, L, R) + query(id * 2 + 2, mid + 1, r, L, R);
}
int ch_p(int id, int l, int r, int L, int R) {
if(L > r || l > R) return 0;
if(L <= l && r <= R) return nm[id];
int mid = (l + r) / 2;
return ch_p(id * 2 + 1, l, mid, L, R) + ch_p(id * 2 + 2, mid + 1, r, L, R);
}
ll find(int u, int v) {
if(hld_pa[u] == hld_pa[v]) {
if(u == v) return 0;
if(d[u] < d[v]) return query(0, 0, n - 1, pos[u] + 1, pos[v]);
else return query(0, 0, n - 1, pos[v] + 1, pos[u]);
}
if(d[hld_pa[u]] < d[hld_pa[v]]) return find(u, pa[hld_pa[v]]) + query(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
else return find(pa[hld_pa[u]], v) + query(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}
bool is;
int cnt_ch_p(int u, int v) {
if(hld_pa[u] == hld_pa[v]) {
if(u == v) return 0;
if(d[u] < d[v]) return ch_p(0, 0, n - 1, pos[u] + 1, pos[v]);
else return ch_p(0, 0, n - 1, pos[v] + 1, pos[u]);
}
if(d[hld_pa[u]] < d[hld_pa[v]]) return cnt_ch_p(u, pa[hld_pa[v]]) + ch_p(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
else return cnt_ch_p(pa[hld_pa[u]], v) + ch_p(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}
void go() {
memset(tree, 0, sizeof(tree));
for(int i = 0; i < m; i++) {
update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
for(int j = 0; j < (int)h[i].size(); j++) {
if(i == 1 && h[i][j] == 0) is = 1;
ll z = find(s[h[i][j]], t[h[i][j]]);
if(i == 1 && h[i][j] == 0) is = 0;
if(z > y[h[i][j]]) {
if(l[h[i][j]] == r[h[i][j]]) {
ans[h[i][j]] = i - 1;
cnt++;
}
else {
r[h[i][j]] = mid[h[i][j]];
mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
}
}
else {
if(l[h[i][j]] == r[h[i][j]]) {
ans[h[i][j]] = i;
cnt++;
}
else {
l[h[i][j]] = mid[h[i][j]] + 1;
mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
}
}
}
h[i].clear();
}
for(int i = 0; i < q; i++) h[mid[i]].pb(i);
}
void solve() {
memset(nm, 0, sizeof(nm));
for(int i = 0; i < m; i++) h[i].clear();
for(int i = 0; i < q; i++) {
if(ans[i] >= 0) h[ans[i]].pb(i);
else ans[i] = 0;
}
for(int i = 0; i < m; i++) {
update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
for(int j = 0; j < (int)h[i].size(); j++) {
if(h[i][j] == 0) is = 1;
ans[h[i][j]] = cnt_ch_p(s[h[i][j]], t[h[i][j]]);
if(h[i][j] == 0) is = 0;
}
}
for(int i = 0; i < q; i++) {
ans[i] = cnt_ch_p(s[i], t[i]) - ans[i];
if(ans[i] > x[i]) ans[i] = -1;
else ans[i] = x[i] - ans[i];
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++) {
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
dfs(0, 0);
hld(0);
for(int i = 0; i < m; i++) {
cin >> p[i] >> c[i];
p[i]--;
if(d[a[p[i]]] > d[b[p[i]]]) cst.pb({c[i], a[p[i]]});
else cst.pb({c[i], b[p[i]]});
}
sort(cst.begin(), cst.end());
for(int i = 0; i < q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
s[i]--;
t[i]--;
l[i] = 0;
r[i] = m - 1;
mid[i] = r[i] / 2;
h[mid[i]].pb(i);
}
while(cnt < q) {
go();
}
solve();
for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
16 ms |
10024 KB |
Output is correct |
6 |
Correct |
22 ms |
10196 KB |
Output is correct |
7 |
Correct |
18 ms |
10176 KB |
Output is correct |
8 |
Correct |
22 ms |
10120 KB |
Output is correct |
9 |
Correct |
22 ms |
10248 KB |
Output is correct |
10 |
Correct |
22 ms |
10244 KB |
Output is correct |
11 |
Correct |
22 ms |
10252 KB |
Output is correct |
12 |
Correct |
23 ms |
10200 KB |
Output is correct |
13 |
Correct |
14 ms |
10324 KB |
Output is correct |
14 |
Correct |
15 ms |
10340 KB |
Output is correct |
15 |
Correct |
17 ms |
10292 KB |
Output is correct |
16 |
Correct |
17 ms |
10196 KB |
Output is correct |
17 |
Correct |
18 ms |
10196 KB |
Output is correct |
18 |
Correct |
17 ms |
10224 KB |
Output is correct |
19 |
Correct |
14 ms |
10168 KB |
Output is correct |
20 |
Correct |
13 ms |
10196 KB |
Output is correct |
21 |
Correct |
14 ms |
10188 KB |
Output is correct |
22 |
Correct |
14 ms |
10276 KB |
Output is correct |
23 |
Correct |
18 ms |
10208 KB |
Output is correct |
24 |
Correct |
24 ms |
10240 KB |
Output is correct |
25 |
Correct |
23 ms |
10292 KB |
Output is correct |
26 |
Correct |
14 ms |
10220 KB |
Output is correct |
27 |
Correct |
15 ms |
10228 KB |
Output is correct |
28 |
Correct |
17 ms |
10196 KB |
Output is correct |
29 |
Correct |
13 ms |
10208 KB |
Output is correct |
30 |
Correct |
25 ms |
10232 KB |
Output is correct |
31 |
Correct |
22 ms |
10160 KB |
Output is correct |
32 |
Correct |
22 ms |
10196 KB |
Output is correct |
33 |
Correct |
14 ms |
10324 KB |
Output is correct |
34 |
Correct |
14 ms |
10296 KB |
Output is correct |
35 |
Correct |
13 ms |
10416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
27 ms |
10160 KB |
Output is correct |
3 |
Correct |
23 ms |
10196 KB |
Output is correct |
4 |
Correct |
22 ms |
10192 KB |
Output is correct |
5 |
Correct |
1872 ms |
29724 KB |
Output is correct |
6 |
Correct |
2429 ms |
32828 KB |
Output is correct |
7 |
Correct |
2463 ms |
32084 KB |
Output is correct |
8 |
Correct |
1757 ms |
28416 KB |
Output is correct |
9 |
Correct |
1646 ms |
28168 KB |
Output is correct |
10 |
Correct |
2795 ms |
36136 KB |
Output is correct |
11 |
Correct |
3250 ms |
36096 KB |
Output is correct |
12 |
Correct |
2843 ms |
35916 KB |
Output is correct |
13 |
Correct |
2841 ms |
36104 KB |
Output is correct |
14 |
Correct |
2955 ms |
36112 KB |
Output is correct |
15 |
Correct |
1066 ms |
44188 KB |
Output is correct |
16 |
Correct |
1124 ms |
44552 KB |
Output is correct |
17 |
Correct |
1133 ms |
43672 KB |
Output is correct |
18 |
Correct |
2599 ms |
36576 KB |
Output is correct |
19 |
Correct |
2496 ms |
36532 KB |
Output is correct |
20 |
Correct |
2241 ms |
36612 KB |
Output is correct |
21 |
Correct |
981 ms |
36400 KB |
Output is correct |
22 |
Correct |
970 ms |
36500 KB |
Output is correct |
23 |
Correct |
1000 ms |
36668 KB |
Output is correct |
24 |
Correct |
976 ms |
36644 KB |
Output is correct |
25 |
Correct |
1994 ms |
36148 KB |
Output is correct |
26 |
Correct |
2173 ms |
36272 KB |
Output is correct |
27 |
Correct |
1991 ms |
36168 KB |
Output is correct |
28 |
Correct |
1183 ms |
34748 KB |
Output is correct |
29 |
Correct |
1209 ms |
33784 KB |
Output is correct |
30 |
Correct |
1689 ms |
34524 KB |
Output is correct |
31 |
Correct |
1566 ms |
34472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
13 ms |
10320 KB |
Output is correct |
3 |
Correct |
13 ms |
10324 KB |
Output is correct |
4 |
Correct |
16 ms |
10416 KB |
Output is correct |
5 |
Correct |
585 ms |
36884 KB |
Output is correct |
6 |
Correct |
578 ms |
36336 KB |
Output is correct |
7 |
Correct |
790 ms |
35448 KB |
Output is correct |
8 |
Correct |
1089 ms |
44780 KB |
Output is correct |
9 |
Correct |
976 ms |
44776 KB |
Output is correct |
10 |
Correct |
991 ms |
44792 KB |
Output is correct |
11 |
Correct |
785 ms |
44916 KB |
Output is correct |
12 |
Correct |
730 ms |
44768 KB |
Output is correct |
13 |
Correct |
777 ms |
44856 KB |
Output is correct |
14 |
Correct |
594 ms |
44044 KB |
Output is correct |
15 |
Correct |
535 ms |
43772 KB |
Output is correct |
16 |
Correct |
662 ms |
44428 KB |
Output is correct |
17 |
Correct |
675 ms |
44272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
16 ms |
10024 KB |
Output is correct |
6 |
Correct |
22 ms |
10196 KB |
Output is correct |
7 |
Correct |
18 ms |
10176 KB |
Output is correct |
8 |
Correct |
22 ms |
10120 KB |
Output is correct |
9 |
Correct |
22 ms |
10248 KB |
Output is correct |
10 |
Correct |
22 ms |
10244 KB |
Output is correct |
11 |
Correct |
22 ms |
10252 KB |
Output is correct |
12 |
Correct |
23 ms |
10200 KB |
Output is correct |
13 |
Correct |
14 ms |
10324 KB |
Output is correct |
14 |
Correct |
15 ms |
10340 KB |
Output is correct |
15 |
Correct |
17 ms |
10292 KB |
Output is correct |
16 |
Correct |
17 ms |
10196 KB |
Output is correct |
17 |
Correct |
18 ms |
10196 KB |
Output is correct |
18 |
Correct |
17 ms |
10224 KB |
Output is correct |
19 |
Correct |
14 ms |
10168 KB |
Output is correct |
20 |
Correct |
13 ms |
10196 KB |
Output is correct |
21 |
Correct |
14 ms |
10188 KB |
Output is correct |
22 |
Correct |
14 ms |
10276 KB |
Output is correct |
23 |
Correct |
18 ms |
10208 KB |
Output is correct |
24 |
Correct |
24 ms |
10240 KB |
Output is correct |
25 |
Correct |
23 ms |
10292 KB |
Output is correct |
26 |
Correct |
14 ms |
10220 KB |
Output is correct |
27 |
Correct |
15 ms |
10228 KB |
Output is correct |
28 |
Correct |
17 ms |
10196 KB |
Output is correct |
29 |
Correct |
13 ms |
10208 KB |
Output is correct |
30 |
Correct |
25 ms |
10232 KB |
Output is correct |
31 |
Correct |
22 ms |
10160 KB |
Output is correct |
32 |
Correct |
22 ms |
10196 KB |
Output is correct |
33 |
Correct |
14 ms |
10324 KB |
Output is correct |
34 |
Correct |
14 ms |
10296 KB |
Output is correct |
35 |
Correct |
13 ms |
10416 KB |
Output is correct |
36 |
Correct |
6 ms |
9684 KB |
Output is correct |
37 |
Correct |
27 ms |
10160 KB |
Output is correct |
38 |
Correct |
23 ms |
10196 KB |
Output is correct |
39 |
Correct |
22 ms |
10192 KB |
Output is correct |
40 |
Correct |
1872 ms |
29724 KB |
Output is correct |
41 |
Correct |
2429 ms |
32828 KB |
Output is correct |
42 |
Correct |
2463 ms |
32084 KB |
Output is correct |
43 |
Correct |
1757 ms |
28416 KB |
Output is correct |
44 |
Correct |
1646 ms |
28168 KB |
Output is correct |
45 |
Correct |
2795 ms |
36136 KB |
Output is correct |
46 |
Correct |
3250 ms |
36096 KB |
Output is correct |
47 |
Correct |
2843 ms |
35916 KB |
Output is correct |
48 |
Correct |
2841 ms |
36104 KB |
Output is correct |
49 |
Correct |
2955 ms |
36112 KB |
Output is correct |
50 |
Correct |
1066 ms |
44188 KB |
Output is correct |
51 |
Correct |
1124 ms |
44552 KB |
Output is correct |
52 |
Correct |
1133 ms |
43672 KB |
Output is correct |
53 |
Correct |
2599 ms |
36576 KB |
Output is correct |
54 |
Correct |
2496 ms |
36532 KB |
Output is correct |
55 |
Correct |
2241 ms |
36612 KB |
Output is correct |
56 |
Correct |
981 ms |
36400 KB |
Output is correct |
57 |
Correct |
970 ms |
36500 KB |
Output is correct |
58 |
Correct |
1000 ms |
36668 KB |
Output is correct |
59 |
Correct |
976 ms |
36644 KB |
Output is correct |
60 |
Correct |
1994 ms |
36148 KB |
Output is correct |
61 |
Correct |
2173 ms |
36272 KB |
Output is correct |
62 |
Correct |
1991 ms |
36168 KB |
Output is correct |
63 |
Correct |
1183 ms |
34748 KB |
Output is correct |
64 |
Correct |
1209 ms |
33784 KB |
Output is correct |
65 |
Correct |
1689 ms |
34524 KB |
Output is correct |
66 |
Correct |
1566 ms |
34472 KB |
Output is correct |
67 |
Correct |
4 ms |
9684 KB |
Output is correct |
68 |
Correct |
13 ms |
10320 KB |
Output is correct |
69 |
Correct |
13 ms |
10324 KB |
Output is correct |
70 |
Correct |
16 ms |
10416 KB |
Output is correct |
71 |
Correct |
585 ms |
36884 KB |
Output is correct |
72 |
Correct |
578 ms |
36336 KB |
Output is correct |
73 |
Correct |
790 ms |
35448 KB |
Output is correct |
74 |
Correct |
1089 ms |
44780 KB |
Output is correct |
75 |
Correct |
976 ms |
44776 KB |
Output is correct |
76 |
Correct |
991 ms |
44792 KB |
Output is correct |
77 |
Correct |
785 ms |
44916 KB |
Output is correct |
78 |
Correct |
730 ms |
44768 KB |
Output is correct |
79 |
Correct |
777 ms |
44856 KB |
Output is correct |
80 |
Correct |
594 ms |
44044 KB |
Output is correct |
81 |
Correct |
535 ms |
43772 KB |
Output is correct |
82 |
Correct |
662 ms |
44428 KB |
Output is correct |
83 |
Correct |
675 ms |
44272 KB |
Output is correct |
84 |
Correct |
1784 ms |
29176 KB |
Output is correct |
85 |
Correct |
1911 ms |
28656 KB |
Output is correct |
86 |
Correct |
1737 ms |
27724 KB |
Output is correct |
87 |
Correct |
2777 ms |
36116 KB |
Output is correct |
88 |
Correct |
2843 ms |
36172 KB |
Output is correct |
89 |
Correct |
2790 ms |
35928 KB |
Output is correct |
90 |
Correct |
2823 ms |
36188 KB |
Output is correct |
91 |
Correct |
2759 ms |
36224 KB |
Output is correct |
92 |
Correct |
1148 ms |
41852 KB |
Output is correct |
93 |
Correct |
1055 ms |
43352 KB |
Output is correct |
94 |
Correct |
2316 ms |
36600 KB |
Output is correct |
95 |
Correct |
2259 ms |
36508 KB |
Output is correct |
96 |
Correct |
2248 ms |
36612 KB |
Output is correct |
97 |
Correct |
2342 ms |
36648 KB |
Output is correct |
98 |
Correct |
1067 ms |
36312 KB |
Output is correct |
99 |
Correct |
996 ms |
36108 KB |
Output is correct |
100 |
Correct |
1050 ms |
36372 KB |
Output is correct |
101 |
Correct |
964 ms |
36432 KB |
Output is correct |
102 |
Correct |
1942 ms |
36788 KB |
Output is correct |
103 |
Correct |
2064 ms |
36712 KB |
Output is correct |
104 |
Correct |
1987 ms |
36596 KB |
Output is correct |
105 |
Correct |
1317 ms |
33656 KB |
Output is correct |
106 |
Correct |
1551 ms |
34880 KB |
Output is correct |
107 |
Correct |
1532 ms |
33896 KB |
Output is correct |
108 |
Correct |
1583 ms |
33748 KB |
Output is correct |