#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
// persistent segment tree (point add range sum)
struct Node {
int val, cnt;
Node *l, *r;
Node() : val(0), cnt(0), l(nullptr), r(nullptr) {}
Node(int x, int y) : val(x), cnt(y), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) : val(ll->val + rr->val), cnt(ll->cnt + rr->cnt), l(ll), r(rr) {}
};
const int mxN = 1e5 + 1;
int n;
Node *segstore[mxN];
Node *SegBuild(int l = 1, int r = n) {
if (l == r) {
return new Node();
}
int mid = (l + r) >> 1;
return new Node(SegBuild(l, mid), SegBuild(mid + 1, r));
}
Node *SegUpdate(Node *seg, int pos, int val, int l = 1, int r = n) {
if (l == r) {
return new Node(seg->val + val, seg->cnt + 1);
}
int mid = (l + r) >> 1;
if (pos <= mid) {
return new Node(SegUpdate(seg->l, pos, val, l, mid), seg->r);
} else {
return new Node(seg->l, SegUpdate(seg->r, pos, val, mid + 1, r));
}
return new Node();
}
pii SegQuery(Node *seg, int &tl, int &tr, int l = 1, int r = n) {
if (tl <= l && r <= tr) {
return {seg->val, seg->cnt};
}
int mid = (l + r) >> 1;
pii res = {0, 0};
pii ret;
if (tl <= mid) {
ret = SegQuery(seg->l, tl, tr, l, mid);
res.ff += ret.ff; res.ss += ret.ss;
}
if (tr > mid) {
ret = SegQuery(seg->r, tl, tr, mid + 1, r);
res.ff += ret.ff; res.ss += ret.ss;
}
return res;
}
// hld
vector<int> adj[mxN];
int par[mxN], rr[mxN], sz[mxN];
int heavy[mxN]; // heavy edge for children
int root[mxN]; // root of heavy edges
int corr[mxN]; // euler tour to map to segtree
void HLDInit(int u = 1, int pp = 0) {
par[u] = pp;
rr[u] = rr[pp] + 1;
sz[u] = 1;
pii big = {-1, -1};
for (int v : adj[u]) {
if (v != pp) {
HLDInit(v, u);
sz[u] += sz[v];
if (sz[v] > big.ff) big = {sz[v], v};
}
}
heavy[u] = big.ss;
}
int segptr = 1;
void HLDProcess(int u = 1, int pp = 0, int high = 1) {
root[u] = high;
corr[u] = segptr++;
if (heavy[u] == -1) return;
HLDProcess(heavy[u], u, high);
for (int v : adj[u]) {
if (v != heavy[u] && v != pp) HLDProcess(v, u, v);
}
}
int HLDLCA(int u, int v) {
while (root[u] != root[v]) {
if (rr[root[u]] > rr[root[v]]) swap(u, v);
v = par[root[v]];
}
return (rr[u] < rr[v] ? u : v);
}
void HLDUpdate(int &ver, int u, int v, int &val) {
// depth[u] < depth[v], update v
if (rr[u] > rr[v]) swap(u, v);
// cerr << "HLDUPDATE " << u << ' ' << v << endl;
segstore[ver] = SegUpdate(segstore[ver - 1], corr[v], val);
}
pii HLDQueryAnces(int &ver, int u, int v) {
int ptr1, ptr2;
pii res = {0, 0};
pii ret;
while (root[u] != root[v]) {
ptr1 = corr[u]; ptr2 = corr[root[u]];
if (ptr1 > ptr2) swap(ptr1, ptr2);
ret = SegQuery(segstore[ver], ptr1, ptr2);
res.ff += ret.ff; res.ss += ret.ss;
u = par[root[u]];
}
if (rr[u] > rr[v]) swap(u, v);
if (u != v) {
ptr1 = corr[heavy[u]]; ptr2 = corr[v];
if (ptr1 > ptr2) swap(ptr1, ptr2);
ret = SegQuery(segstore[ver], ptr1, ptr2);
res.ff += ret.ff; res.ss += ret.ss;
}
return res;
}
pii HLDQuery(int &ver, int u, int v) {
int lca = HLDLCA(u, v);
pii lhs = HLDQueryAnces(ver, u, lca);
pii rhs = HLDQueryAnces(ver, v, lca);
// cerr << "HLDQUERY\n";
// cerr << ver << ' ' << u << ' ' << v << ' ' << lca << endl;
// cerr << lhs.ff << ' ' << lhs.ss << endl;
// cerr << rhs.ff << ' ' << rhs.ss << endl;
return {lhs.ff + rhs.ff, lhs.ss + rhs.ss};
}
void init() {
// init
}
void solve() {
// solve
int m, q;
cin >> n >> m >> q;
pii edges[n];
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
edges[i] = {u, v};
}
HLDInit();
HLDProcess();
pii updates[m + 1];
for (int i = 1; i <= m; i++) {
cin >> updates[i].ff >> updates[i].ss;
}
sort(updates + 1, updates + m + 1, [&](pii &lhs, pii &rhs) { return lhs.ss < rhs.ss; });
segstore[0] = SegBuild();
for (int i = 1; i <= m; i++) {
HLDUpdate(i, edges[updates[i].ff].ff, edges[updates[i].ff].ss, updates[i].ss);
}
while (q--) {
int s, t, x, y;
cin >> s >> t >> x >> y;
int lb = 0, rb = m;
pii ret;
while (lb < rb) {
int mid = (lb + rb + 1) >> 1;
ret = HLDQuery(mid, s, t);
if (ret.ff <= y) {
lb = mid;
} else {
rb = mid - 1;
}
}
ret = HLDQuery(lb, s, t);
// cerr << lb << ' ' << ret.ff << ' ' << ret.ss << endl;
// cerr << HLDQuery(m, s, t).ff << ' ' << HLDQuery(m, s, t).ss << endl;
x -= HLDQuery(m, s, t).ss - HLDQuery(lb, s, t).ss;
cout << (x < 0 ? -1 : x) << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
init(); solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5272 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
9 ms |
6576 KB |
Output is correct |
6 |
Correct |
13 ms |
6576 KB |
Output is correct |
7 |
Correct |
11 ms |
6232 KB |
Output is correct |
8 |
Correct |
14 ms |
6748 KB |
Output is correct |
9 |
Correct |
13 ms |
6748 KB |
Output is correct |
10 |
Correct |
14 ms |
6916 KB |
Output is correct |
11 |
Correct |
17 ms |
6920 KB |
Output is correct |
12 |
Correct |
15 ms |
6744 KB |
Output is correct |
13 |
Correct |
11 ms |
7012 KB |
Output is correct |
14 |
Correct |
10 ms |
6980 KB |
Output is correct |
15 |
Correct |
11 ms |
6748 KB |
Output is correct |
16 |
Correct |
12 ms |
6928 KB |
Output is correct |
17 |
Correct |
12 ms |
6748 KB |
Output is correct |
18 |
Correct |
11 ms |
6744 KB |
Output is correct |
19 |
Correct |
8 ms |
6744 KB |
Output is correct |
20 |
Correct |
8 ms |
7000 KB |
Output is correct |
21 |
Correct |
8 ms |
6748 KB |
Output is correct |
22 |
Correct |
8 ms |
6748 KB |
Output is correct |
23 |
Correct |
12 ms |
6748 KB |
Output is correct |
24 |
Correct |
13 ms |
6744 KB |
Output is correct |
25 |
Correct |
14 ms |
6748 KB |
Output is correct |
26 |
Correct |
10 ms |
6748 KB |
Output is correct |
27 |
Correct |
10 ms |
6748 KB |
Output is correct |
28 |
Correct |
12 ms |
6744 KB |
Output is correct |
29 |
Correct |
8 ms |
6904 KB |
Output is correct |
30 |
Correct |
14 ms |
6744 KB |
Output is correct |
31 |
Correct |
13 ms |
6744 KB |
Output is correct |
32 |
Correct |
13 ms |
6748 KB |
Output is correct |
33 |
Correct |
8 ms |
7004 KB |
Output is correct |
34 |
Correct |
8 ms |
7004 KB |
Output is correct |
35 |
Correct |
8 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
14 ms |
6920 KB |
Output is correct |
3 |
Correct |
14 ms |
6748 KB |
Output is correct |
4 |
Correct |
14 ms |
6744 KB |
Output is correct |
5 |
Correct |
2476 ms |
103828 KB |
Output is correct |
6 |
Correct |
3555 ms |
89424 KB |
Output is correct |
7 |
Correct |
3123 ms |
79196 KB |
Output is correct |
8 |
Correct |
2196 ms |
76796 KB |
Output is correct |
9 |
Correct |
2040 ms |
81180 KB |
Output is correct |
10 |
Correct |
4223 ms |
112976 KB |
Output is correct |
11 |
Correct |
4531 ms |
113072 KB |
Output is correct |
12 |
Correct |
4402 ms |
113184 KB |
Output is correct |
13 |
Correct |
4481 ms |
113152 KB |
Output is correct |
14 |
Correct |
4456 ms |
113004 KB |
Output is correct |
15 |
Correct |
2585 ms |
119004 KB |
Output is correct |
16 |
Correct |
2512 ms |
119548 KB |
Output is correct |
17 |
Correct |
2618 ms |
118640 KB |
Output is correct |
18 |
Correct |
4979 ms |
112748 KB |
Output is correct |
19 |
Correct |
4844 ms |
112800 KB |
Output is correct |
20 |
Correct |
4842 ms |
112952 KB |
Output is correct |
21 |
Correct |
2019 ms |
112668 KB |
Output is correct |
22 |
Correct |
1911 ms |
112832 KB |
Output is correct |
23 |
Correct |
2044 ms |
112620 KB |
Output is correct |
24 |
Correct |
2004 ms |
112744 KB |
Output is correct |
25 |
Correct |
2950 ms |
111828 KB |
Output is correct |
26 |
Correct |
3078 ms |
114208 KB |
Output is correct |
27 |
Correct |
3303 ms |
114188 KB |
Output is correct |
28 |
Correct |
1357 ms |
112968 KB |
Output is correct |
29 |
Correct |
1378 ms |
113084 KB |
Output is correct |
30 |
Correct |
2421 ms |
113060 KB |
Output is correct |
31 |
Correct |
2084 ms |
113444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5212 KB |
Output is correct |
2 |
Correct |
11 ms |
7004 KB |
Output is correct |
3 |
Correct |
8 ms |
7000 KB |
Output is correct |
4 |
Correct |
11 ms |
7032 KB |
Output is correct |
5 |
Correct |
1253 ms |
87620 KB |
Output is correct |
6 |
Correct |
1092 ms |
75132 KB |
Output is correct |
7 |
Correct |
1679 ms |
98048 KB |
Output is correct |
8 |
Correct |
2527 ms |
119424 KB |
Output is correct |
9 |
Correct |
2527 ms |
119428 KB |
Output is correct |
10 |
Correct |
2620 ms |
119456 KB |
Output is correct |
11 |
Correct |
1870 ms |
120032 KB |
Output is correct |
12 |
Correct |
1908 ms |
117928 KB |
Output is correct |
13 |
Correct |
1864 ms |
120236 KB |
Output is correct |
14 |
Correct |
908 ms |
119376 KB |
Output is correct |
15 |
Correct |
720 ms |
119292 KB |
Output is correct |
16 |
Correct |
1157 ms |
119636 KB |
Output is correct |
17 |
Correct |
1198 ms |
119380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5272 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
9 ms |
6576 KB |
Output is correct |
6 |
Correct |
13 ms |
6576 KB |
Output is correct |
7 |
Correct |
11 ms |
6232 KB |
Output is correct |
8 |
Correct |
14 ms |
6748 KB |
Output is correct |
9 |
Correct |
13 ms |
6748 KB |
Output is correct |
10 |
Correct |
14 ms |
6916 KB |
Output is correct |
11 |
Correct |
17 ms |
6920 KB |
Output is correct |
12 |
Correct |
15 ms |
6744 KB |
Output is correct |
13 |
Correct |
11 ms |
7012 KB |
Output is correct |
14 |
Correct |
10 ms |
6980 KB |
Output is correct |
15 |
Correct |
11 ms |
6748 KB |
Output is correct |
16 |
Correct |
12 ms |
6928 KB |
Output is correct |
17 |
Correct |
12 ms |
6748 KB |
Output is correct |
18 |
Correct |
11 ms |
6744 KB |
Output is correct |
19 |
Correct |
8 ms |
6744 KB |
Output is correct |
20 |
Correct |
8 ms |
7000 KB |
Output is correct |
21 |
Correct |
8 ms |
6748 KB |
Output is correct |
22 |
Correct |
8 ms |
6748 KB |
Output is correct |
23 |
Correct |
12 ms |
6748 KB |
Output is correct |
24 |
Correct |
13 ms |
6744 KB |
Output is correct |
25 |
Correct |
14 ms |
6748 KB |
Output is correct |
26 |
Correct |
10 ms |
6748 KB |
Output is correct |
27 |
Correct |
10 ms |
6748 KB |
Output is correct |
28 |
Correct |
12 ms |
6744 KB |
Output is correct |
29 |
Correct |
8 ms |
6904 KB |
Output is correct |
30 |
Correct |
14 ms |
6744 KB |
Output is correct |
31 |
Correct |
13 ms |
6744 KB |
Output is correct |
32 |
Correct |
13 ms |
6748 KB |
Output is correct |
33 |
Correct |
8 ms |
7004 KB |
Output is correct |
34 |
Correct |
8 ms |
7004 KB |
Output is correct |
35 |
Correct |
8 ms |
7004 KB |
Output is correct |
36 |
Correct |
1 ms |
5212 KB |
Output is correct |
37 |
Correct |
14 ms |
6920 KB |
Output is correct |
38 |
Correct |
14 ms |
6748 KB |
Output is correct |
39 |
Correct |
14 ms |
6744 KB |
Output is correct |
40 |
Correct |
2476 ms |
103828 KB |
Output is correct |
41 |
Correct |
3555 ms |
89424 KB |
Output is correct |
42 |
Correct |
3123 ms |
79196 KB |
Output is correct |
43 |
Correct |
2196 ms |
76796 KB |
Output is correct |
44 |
Correct |
2040 ms |
81180 KB |
Output is correct |
45 |
Correct |
4223 ms |
112976 KB |
Output is correct |
46 |
Correct |
4531 ms |
113072 KB |
Output is correct |
47 |
Correct |
4402 ms |
113184 KB |
Output is correct |
48 |
Correct |
4481 ms |
113152 KB |
Output is correct |
49 |
Correct |
4456 ms |
113004 KB |
Output is correct |
50 |
Correct |
2585 ms |
119004 KB |
Output is correct |
51 |
Correct |
2512 ms |
119548 KB |
Output is correct |
52 |
Correct |
2618 ms |
118640 KB |
Output is correct |
53 |
Correct |
4979 ms |
112748 KB |
Output is correct |
54 |
Correct |
4844 ms |
112800 KB |
Output is correct |
55 |
Correct |
4842 ms |
112952 KB |
Output is correct |
56 |
Correct |
2019 ms |
112668 KB |
Output is correct |
57 |
Correct |
1911 ms |
112832 KB |
Output is correct |
58 |
Correct |
2044 ms |
112620 KB |
Output is correct |
59 |
Correct |
2004 ms |
112744 KB |
Output is correct |
60 |
Correct |
2950 ms |
111828 KB |
Output is correct |
61 |
Correct |
3078 ms |
114208 KB |
Output is correct |
62 |
Correct |
3303 ms |
114188 KB |
Output is correct |
63 |
Correct |
1357 ms |
112968 KB |
Output is correct |
64 |
Correct |
1378 ms |
113084 KB |
Output is correct |
65 |
Correct |
2421 ms |
113060 KB |
Output is correct |
66 |
Correct |
2084 ms |
113444 KB |
Output is correct |
67 |
Correct |
2 ms |
5212 KB |
Output is correct |
68 |
Correct |
11 ms |
7004 KB |
Output is correct |
69 |
Correct |
8 ms |
7000 KB |
Output is correct |
70 |
Correct |
11 ms |
7032 KB |
Output is correct |
71 |
Correct |
1253 ms |
87620 KB |
Output is correct |
72 |
Correct |
1092 ms |
75132 KB |
Output is correct |
73 |
Correct |
1679 ms |
98048 KB |
Output is correct |
74 |
Correct |
2527 ms |
119424 KB |
Output is correct |
75 |
Correct |
2527 ms |
119428 KB |
Output is correct |
76 |
Correct |
2620 ms |
119456 KB |
Output is correct |
77 |
Correct |
1870 ms |
120032 KB |
Output is correct |
78 |
Correct |
1908 ms |
117928 KB |
Output is correct |
79 |
Correct |
1864 ms |
120236 KB |
Output is correct |
80 |
Correct |
908 ms |
119376 KB |
Output is correct |
81 |
Correct |
720 ms |
119292 KB |
Output is correct |
82 |
Correct |
1157 ms |
119636 KB |
Output is correct |
83 |
Correct |
1198 ms |
119380 KB |
Output is correct |
84 |
Correct |
2684 ms |
102372 KB |
Output is correct |
85 |
Correct |
2839 ms |
88156 KB |
Output is correct |
86 |
Correct |
2530 ms |
66132 KB |
Output is correct |
87 |
Correct |
4595 ms |
112996 KB |
Output is correct |
88 |
Correct |
4407 ms |
112764 KB |
Output is correct |
89 |
Correct |
4545 ms |
112984 KB |
Output is correct |
90 |
Correct |
4555 ms |
112808 KB |
Output is correct |
91 |
Correct |
4598 ms |
113140 KB |
Output is correct |
92 |
Correct |
2803 ms |
116532 KB |
Output is correct |
93 |
Correct |
2659 ms |
118020 KB |
Output is correct |
94 |
Correct |
4897 ms |
113060 KB |
Output is correct |
95 |
Correct |
4948 ms |
112792 KB |
Output is correct |
96 |
Correct |
4907 ms |
113088 KB |
Output is correct |
97 |
Correct |
4893 ms |
112716 KB |
Output is correct |
98 |
Correct |
2033 ms |
112500 KB |
Output is correct |
99 |
Correct |
2037 ms |
112516 KB |
Output is correct |
100 |
Correct |
2103 ms |
112832 KB |
Output is correct |
101 |
Correct |
2037 ms |
112700 KB |
Output is correct |
102 |
Correct |
2910 ms |
114460 KB |
Output is correct |
103 |
Correct |
3054 ms |
114332 KB |
Output is correct |
104 |
Correct |
3055 ms |
114168 KB |
Output is correct |
105 |
Correct |
1568 ms |
113092 KB |
Output is correct |
106 |
Correct |
1678 ms |
113044 KB |
Output is correct |
107 |
Correct |
1968 ms |
112784 KB |
Output is correct |
108 |
Correct |
1989 ms |
113148 KB |
Output is correct |