/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
struct query {
int s, t, x, y;
query(int s, int t, int x, int y) : s(s), t(t), x(x), y(y) {}
};
vi pos, G[mxN];
vii edges, points;
vector<query> queries;
pii euler_tour[20][2 * mxN];
int n, m, q, a[mxN], ans[mxN], cp[mxN];
int tin[mxN], tout[mxN], dep[mxN], ap[mxN], timer, ecnt;
void dfs(int v, int p) {
tin[v] = ++timer, dep[v] = dep[p] + 1;
euler_tour[0][++ecnt] = pair{dep[v], v}, ap[v] = ecnt;
for(int u : G[v]) {
if(u == p) continue;
dfs(u, v);
euler_tour[0][++ecnt] = pair{dep[v], v};
}
tout[v] = timer;
}
void build_sparse() {
for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
euler_tour[i][j] = min(euler_tour[i - 1][j], euler_tour[i - 1][j + p]);
}
int LCA(int u, int v) {
int l = ap[u], r = ap[v];
if(l > r) swap(l, r);
int len = r - l + 1, lg_len = __lg(len);
return min(euler_tour[lg_len][l], euler_tour[lg_len][r - (1 << lg_len) + 1]).ss;
}
pii fenw[mxN];
void update(int idx, int val1, int val2) {
for(; idx <= n; idx += (idx & (-idx)))
fenw[idx].ff += val1, fenw[idx].ss += val2;
}
void update_range(int l, int r, int val1, int val2) {
update(l, val1, val2);
update(r + 1, -val1, -val2);
}
pii get(int idx) {
pii res = pair{0, 0};
for(; idx; idx -= (idx & (-idx)))
res.ff += fenw[idx].ff, res.ss += fenw[idx].ss;
return res;
}
pii add(pii x, pii y) {
return pair{x.ff + y.ff, x.ss + y.ss};
}
pii sub(pii x, pii y) {
return pair{x.ff - y.ff, x.ss - y.ss};
}
pii mul(pii x, int val) {
return pair{x.ff * val, x.ss * val};
}
void pbs(int l, int r, vi &all_query) {
if(l > r) return;
vi left, right;
int mid = (l + r) >> 1;
for(int i = l; i <= mid; ++i) {
pii tmp = points[i], edge = edges[tmp.ff];
if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
update_range(tin[edge.ss], tout[edge.ss], tmp.ss, 1);
}
for(auto &idx : all_query) {
auto [s, t, x, y] = queries[idx];
int lca = LCA(s, t);
pii res = pair{0, 0};
res = add(res, get(tin[s]));
res = add(res, get(tin[t]));
res = sub(res, mul(get(tin[lca]), 2));
if(res.ff <= y) {
ans[idx] = max(ans[idx], x - (cp[s] + cp[t] - 2 * cp[lca] - res.ss));
right.emplace_back(idx);
}
else left.emplace_back(idx);
}
if(l == r) {
pii tmp = points[mid], edge = edges[tmp.ff];
if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
update_range(tin[edge.ss], tout[edge.ss], -tmp.ss, -1);
return;
}
if(!right.empty()) {
pbs(mid + 1, r, right);
}
for(int i = l; i <= mid; ++i) {
pii tmp = points[i], edge = edges[tmp.ff];
if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
update_range(tin[edge.ss], tout[edge.ss], -tmp.ss, -1);
}
if(!left.empty()) {
pbs(l, mid - 1, left);
}
}
void solve() {
cin >> n >> m >> q;
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
edges.emplace_back(u, v);
}
dfs(1, 0);
build_sparse();
for(int i = 1; i <= m; ++i) {
int p, c; cin >> p >> c;
points.emplace_back(--p, c);
pii edge = edges[p];
if(dep[edge.ff] > dep[edge.ss])
swap(edge.ff, edge.ss);
++cp[edge.ss];
}
auto dfs_cp = [&](auto self, int v, int p) -> void {
for(int u : G[v]) {
if(u == p) continue;
cp[u] += cp[v];
self(self, u, v);
}
};
dfs_cp(dfs_cp, 1, 0);
sort(all(points), [&](pii &x, pii &y) {
return x.ss < y.ss;
});
for(int i = 1; i <= q; ++i) {
int s, t, x, y;
cin >> s >> t >> x >> y;
queries.emplace_back(s, t, x, y);
int lca = LCA(s, t);
ans[i - 1] = max(-1ll, x - (cp[s] + cp[t] - 2 * cp[lca]));
}
vi idx(q); iota(all(idx), 0);
pbs(0, m - 1, idx);
for(int i = 0; i < q; ++i)
cout << ans[i] << "\n";
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
5 ms |
6192 KB |
Output is correct |
6 |
Correct |
6 ms |
6388 KB |
Output is correct |
7 |
Correct |
7 ms |
5972 KB |
Output is correct |
8 |
Correct |
9 ms |
6344 KB |
Output is correct |
9 |
Correct |
7 ms |
6336 KB |
Output is correct |
10 |
Correct |
7 ms |
6356 KB |
Output is correct |
11 |
Correct |
7 ms |
6356 KB |
Output is correct |
12 |
Correct |
7 ms |
6352 KB |
Output is correct |
13 |
Correct |
7 ms |
6356 KB |
Output is correct |
14 |
Correct |
6 ms |
6352 KB |
Output is correct |
15 |
Correct |
6 ms |
6356 KB |
Output is correct |
16 |
Correct |
10 ms |
6356 KB |
Output is correct |
17 |
Correct |
8 ms |
6400 KB |
Output is correct |
18 |
Correct |
8 ms |
6400 KB |
Output is correct |
19 |
Correct |
6 ms |
6324 KB |
Output is correct |
20 |
Correct |
6 ms |
6356 KB |
Output is correct |
21 |
Correct |
7 ms |
6356 KB |
Output is correct |
22 |
Correct |
8 ms |
6356 KB |
Output is correct |
23 |
Correct |
7 ms |
6324 KB |
Output is correct |
24 |
Correct |
6 ms |
6364 KB |
Output is correct |
25 |
Correct |
7 ms |
6324 KB |
Output is correct |
26 |
Correct |
6 ms |
6356 KB |
Output is correct |
27 |
Correct |
5 ms |
6320 KB |
Output is correct |
28 |
Correct |
6 ms |
6340 KB |
Output is correct |
29 |
Correct |
6 ms |
6484 KB |
Output is correct |
30 |
Correct |
8 ms |
6356 KB |
Output is correct |
31 |
Correct |
7 ms |
6356 KB |
Output is correct |
32 |
Correct |
7 ms |
6336 KB |
Output is correct |
33 |
Correct |
8 ms |
6468 KB |
Output is correct |
34 |
Correct |
9 ms |
6356 KB |
Output is correct |
35 |
Correct |
7 ms |
6452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5028 KB |
Output is correct |
2 |
Correct |
7 ms |
6340 KB |
Output is correct |
3 |
Correct |
8 ms |
6340 KB |
Output is correct |
4 |
Correct |
8 ms |
6448 KB |
Output is correct |
5 |
Correct |
371 ms |
80652 KB |
Output is correct |
6 |
Correct |
427 ms |
62512 KB |
Output is correct |
7 |
Correct |
460 ms |
71708 KB |
Output is correct |
8 |
Correct |
324 ms |
71780 KB |
Output is correct |
9 |
Correct |
331 ms |
70228 KB |
Output is correct |
10 |
Correct |
547 ms |
82484 KB |
Output is correct |
11 |
Correct |
504 ms |
82436 KB |
Output is correct |
12 |
Correct |
619 ms |
82280 KB |
Output is correct |
13 |
Correct |
605 ms |
82152 KB |
Output is correct |
14 |
Correct |
563 ms |
82340 KB |
Output is correct |
15 |
Correct |
508 ms |
87572 KB |
Output is correct |
16 |
Correct |
524 ms |
88008 KB |
Output is correct |
17 |
Correct |
522 ms |
87296 KB |
Output is correct |
18 |
Correct |
530 ms |
81792 KB |
Output is correct |
19 |
Correct |
578 ms |
81844 KB |
Output is correct |
20 |
Correct |
576 ms |
81812 KB |
Output is correct |
21 |
Correct |
541 ms |
84896 KB |
Output is correct |
22 |
Correct |
585 ms |
84952 KB |
Output is correct |
23 |
Correct |
516 ms |
85092 KB |
Output is correct |
24 |
Correct |
559 ms |
84972 KB |
Output is correct |
25 |
Correct |
449 ms |
83268 KB |
Output is correct |
26 |
Correct |
434 ms |
82968 KB |
Output is correct |
27 |
Correct |
498 ms |
83452 KB |
Output is correct |
28 |
Correct |
274 ms |
82876 KB |
Output is correct |
29 |
Correct |
258 ms |
84804 KB |
Output is correct |
30 |
Correct |
328 ms |
83024 KB |
Output is correct |
31 |
Correct |
393 ms |
83132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
6 ms |
6452 KB |
Output is correct |
3 |
Correct |
6 ms |
6444 KB |
Output is correct |
4 |
Correct |
7 ms |
6452 KB |
Output is correct |
5 |
Correct |
360 ms |
82972 KB |
Output is correct |
6 |
Correct |
330 ms |
81352 KB |
Output is correct |
7 |
Correct |
337 ms |
56548 KB |
Output is correct |
8 |
Correct |
506 ms |
88024 KB |
Output is correct |
9 |
Correct |
523 ms |
87852 KB |
Output is correct |
10 |
Correct |
459 ms |
88168 KB |
Output is correct |
11 |
Correct |
350 ms |
87760 KB |
Output is correct |
12 |
Correct |
392 ms |
87400 KB |
Output is correct |
13 |
Correct |
401 ms |
87408 KB |
Output is correct |
14 |
Correct |
337 ms |
87412 KB |
Output is correct |
15 |
Correct |
290 ms |
87504 KB |
Output is correct |
16 |
Correct |
309 ms |
87480 KB |
Output is correct |
17 |
Correct |
309 ms |
87552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
5 ms |
6192 KB |
Output is correct |
6 |
Correct |
6 ms |
6388 KB |
Output is correct |
7 |
Correct |
7 ms |
5972 KB |
Output is correct |
8 |
Correct |
9 ms |
6344 KB |
Output is correct |
9 |
Correct |
7 ms |
6336 KB |
Output is correct |
10 |
Correct |
7 ms |
6356 KB |
Output is correct |
11 |
Correct |
7 ms |
6356 KB |
Output is correct |
12 |
Correct |
7 ms |
6352 KB |
Output is correct |
13 |
Correct |
7 ms |
6356 KB |
Output is correct |
14 |
Correct |
6 ms |
6352 KB |
Output is correct |
15 |
Correct |
6 ms |
6356 KB |
Output is correct |
16 |
Correct |
10 ms |
6356 KB |
Output is correct |
17 |
Correct |
8 ms |
6400 KB |
Output is correct |
18 |
Correct |
8 ms |
6400 KB |
Output is correct |
19 |
Correct |
6 ms |
6324 KB |
Output is correct |
20 |
Correct |
6 ms |
6356 KB |
Output is correct |
21 |
Correct |
7 ms |
6356 KB |
Output is correct |
22 |
Correct |
8 ms |
6356 KB |
Output is correct |
23 |
Correct |
7 ms |
6324 KB |
Output is correct |
24 |
Correct |
6 ms |
6364 KB |
Output is correct |
25 |
Correct |
7 ms |
6324 KB |
Output is correct |
26 |
Correct |
6 ms |
6356 KB |
Output is correct |
27 |
Correct |
5 ms |
6320 KB |
Output is correct |
28 |
Correct |
6 ms |
6340 KB |
Output is correct |
29 |
Correct |
6 ms |
6484 KB |
Output is correct |
30 |
Correct |
8 ms |
6356 KB |
Output is correct |
31 |
Correct |
7 ms |
6356 KB |
Output is correct |
32 |
Correct |
7 ms |
6336 KB |
Output is correct |
33 |
Correct |
8 ms |
6468 KB |
Output is correct |
34 |
Correct |
9 ms |
6356 KB |
Output is correct |
35 |
Correct |
7 ms |
6452 KB |
Output is correct |
36 |
Correct |
4 ms |
5028 KB |
Output is correct |
37 |
Correct |
7 ms |
6340 KB |
Output is correct |
38 |
Correct |
8 ms |
6340 KB |
Output is correct |
39 |
Correct |
8 ms |
6448 KB |
Output is correct |
40 |
Correct |
371 ms |
80652 KB |
Output is correct |
41 |
Correct |
427 ms |
62512 KB |
Output is correct |
42 |
Correct |
460 ms |
71708 KB |
Output is correct |
43 |
Correct |
324 ms |
71780 KB |
Output is correct |
44 |
Correct |
331 ms |
70228 KB |
Output is correct |
45 |
Correct |
547 ms |
82484 KB |
Output is correct |
46 |
Correct |
504 ms |
82436 KB |
Output is correct |
47 |
Correct |
619 ms |
82280 KB |
Output is correct |
48 |
Correct |
605 ms |
82152 KB |
Output is correct |
49 |
Correct |
563 ms |
82340 KB |
Output is correct |
50 |
Correct |
508 ms |
87572 KB |
Output is correct |
51 |
Correct |
524 ms |
88008 KB |
Output is correct |
52 |
Correct |
522 ms |
87296 KB |
Output is correct |
53 |
Correct |
530 ms |
81792 KB |
Output is correct |
54 |
Correct |
578 ms |
81844 KB |
Output is correct |
55 |
Correct |
576 ms |
81812 KB |
Output is correct |
56 |
Correct |
541 ms |
84896 KB |
Output is correct |
57 |
Correct |
585 ms |
84952 KB |
Output is correct |
58 |
Correct |
516 ms |
85092 KB |
Output is correct |
59 |
Correct |
559 ms |
84972 KB |
Output is correct |
60 |
Correct |
449 ms |
83268 KB |
Output is correct |
61 |
Correct |
434 ms |
82968 KB |
Output is correct |
62 |
Correct |
498 ms |
83452 KB |
Output is correct |
63 |
Correct |
274 ms |
82876 KB |
Output is correct |
64 |
Correct |
258 ms |
84804 KB |
Output is correct |
65 |
Correct |
328 ms |
83024 KB |
Output is correct |
66 |
Correct |
393 ms |
83132 KB |
Output is correct |
67 |
Correct |
2 ms |
5076 KB |
Output is correct |
68 |
Correct |
6 ms |
6452 KB |
Output is correct |
69 |
Correct |
6 ms |
6444 KB |
Output is correct |
70 |
Correct |
7 ms |
6452 KB |
Output is correct |
71 |
Correct |
360 ms |
82972 KB |
Output is correct |
72 |
Correct |
330 ms |
81352 KB |
Output is correct |
73 |
Correct |
337 ms |
56548 KB |
Output is correct |
74 |
Correct |
506 ms |
88024 KB |
Output is correct |
75 |
Correct |
523 ms |
87852 KB |
Output is correct |
76 |
Correct |
459 ms |
88168 KB |
Output is correct |
77 |
Correct |
350 ms |
87760 KB |
Output is correct |
78 |
Correct |
392 ms |
87400 KB |
Output is correct |
79 |
Correct |
401 ms |
87408 KB |
Output is correct |
80 |
Correct |
337 ms |
87412 KB |
Output is correct |
81 |
Correct |
290 ms |
87504 KB |
Output is correct |
82 |
Correct |
309 ms |
87480 KB |
Output is correct |
83 |
Correct |
309 ms |
87552 KB |
Output is correct |
84 |
Correct |
363 ms |
69916 KB |
Output is correct |
85 |
Correct |
350 ms |
51148 KB |
Output is correct |
86 |
Correct |
291 ms |
49964 KB |
Output is correct |
87 |
Correct |
519 ms |
82100 KB |
Output is correct |
88 |
Correct |
593 ms |
82024 KB |
Output is correct |
89 |
Correct |
563 ms |
81808 KB |
Output is correct |
90 |
Correct |
588 ms |
81672 KB |
Output is correct |
91 |
Correct |
556 ms |
81744 KB |
Output is correct |
92 |
Correct |
519 ms |
84996 KB |
Output is correct |
93 |
Correct |
487 ms |
85896 KB |
Output is correct |
94 |
Correct |
570 ms |
80924 KB |
Output is correct |
95 |
Correct |
552 ms |
80984 KB |
Output is correct |
96 |
Correct |
603 ms |
80952 KB |
Output is correct |
97 |
Correct |
529 ms |
80828 KB |
Output is correct |
98 |
Correct |
590 ms |
84992 KB |
Output is correct |
99 |
Correct |
494 ms |
84864 KB |
Output is correct |
100 |
Correct |
587 ms |
84800 KB |
Output is correct |
101 |
Correct |
474 ms |
84984 KB |
Output is correct |
102 |
Correct |
426 ms |
82044 KB |
Output is correct |
103 |
Correct |
420 ms |
82484 KB |
Output is correct |
104 |
Correct |
400 ms |
82296 KB |
Output is correct |
105 |
Correct |
266 ms |
82588 KB |
Output is correct |
106 |
Correct |
257 ms |
82992 KB |
Output is correct |
107 |
Correct |
322 ms |
83180 KB |
Output is correct |
108 |
Correct |
329 ms |
83184 KB |
Output is correct |