#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
#define int ll
const int K = 19;
struct BIT{
int n;
vector<ll> sm;
BIT(int _n){
n = _n;
sm.resize(n);
}
void add(int in, ll x){
in++;
while(in <= n) sm[in-1]+=x, in+=in&-in;
}
void add(int l, int r, ll x){
add(l, x);
if(r+1 < n) add(r+1, -x);
}
ll get(int in){
in++;
ll s = 0;
while(in >= 1) s+=sm[in-1], in-=in&-in;
return s;
}
};
struct query{
int a, b, c;
ll g, s;
int i;
query(){}
query(int _a, int _b, int _c, ll _g, ll _s, int _i): a(_a), b(_b), c(_c), g(_g), s(_s), i(_i) {}
};
int n, m, q;
vector<pair<int, ll>> c;
vector<vector<int>> tree;
vector<int> depth, pos, sz;
vector<int> anc[K];
BIT bit1(0), bit2(0);
vector<ll> ans;
vector<pair<int, int>> edges;
vector<query> Q;
int intime = 0;
void dfs(int nd, int ss, int d){
pos[nd] = intime++;
depth[nd] = d;
if(ss != -1) anc[0][nd] = ss;
for(int x: tree[nd]) if(x != ss) dfs(x, nd, d+1), sz[nd]+=sz[x];
}
int get_anc(int nd, int d){
for(int i = 0; i < K; i++){
if(d&1) nd = anc[i][nd];
d>>=1;
}
return nd;
}
int lca(int a, int b){
if(depth[a] > depth[b]) swap(a, b);
b = get_anc(b, depth[b]-depth[a]);
if(a == b) return a;
for(int i = K-1; i >= 0; i--) if(anc[i][a] != anc[i][b])
a = anc[i][a], b = anc[i][b];
return anc[0][a];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
c.resize(m);
tree.resize(n);
depth.resize(n);
pos.resize(n);
sz.assign(n, 1);
fill(anc, anc+K, vector<int>(n, 0));
bit1 = BIT(n), bit2 = BIT(n);
ans.resize(q);
for(int i = 0; i < n-1; i++){
int a, b; cin >> a >> b; a--, b--;
tree[a].pb(b);
tree[b].pb(a);
edges.pb({a, b});
}
dfs(0, -1, 0);
for(int p = 1; p < K; p++) for(int i = 0; i < n; i++)
anc[p][i] = anc[p-1][anc[p-1][i]];
for(auto &[i, x]: c){
cin >> i >> x, i--;
auto [a, b] = edges[i];
if(depth[a] > depth[b]) i = a;
else i = b;
bit1.add(pos[i], pos[i]+sz[i]-1, x);
}
sort(c.begin(), c.end(), [](pair<int, ll> a, pair<int, ll> b){
return make_pair(a.sc, a.f) > make_pair(b.sc, b.f);
});
c.insert(c.begin(), {0, 0});
for(int i = 0; i < q; i++){
int a, b; ll g, s; cin >> a >> b >> g >> s;
a--, b--;
int c = lca(a, b);
a = pos[a], b = pos[b], c = pos[c];
Q.pb(query(a, b, c, g, s, i));
}
function<void(int, int, vector<int>)> pbs = [&](int l, int r, const vector<int>& Qi){
if(Qi.empty()) return;
if(l == r){
bit2.add(pos[c[l].f], pos[c[l].f]+sz[c[l].f]-1, 1);
for(int i: Qi){
ans[Q[i].i] = Q[i].g-bit2.get(Q[i].a)-bit2.get(Q[i].b)+bit2.get(Q[i].c)*2;
ans[Q[i].i] = max(ans[Q[i].i], -1LL);
}
bit2.add(pos[c[l].f], pos[c[l].f]+sz[c[l].f]-1, -1);
return;
}
int md = (l+r)/2;
for(int i = l; i <= md; i++){
bit1.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, -c[i].sc);
bit2.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, 1);
}
vector<int> A, B;
for(int i: Qi){
if(bit1.get(Q[i].a)+bit1.get(Q[i].b)-bit1.get(Q[i].c)*2 > Q[i].s) B.pb(i);
else A.pb(i);
}
pbs(md+1, r, B);
for(int i = l; i <= md; i++){
bit1.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, c[i].sc);
bit2.add(pos[c[i].f], pos[c[i].f]+sz[c[i].f]-1, -1);
}
pbs(l, md, A);
};
vector<int> Qi;
for(int i = 0; i < q; i++) Qi.pb(i);
pbs(0, m, Qi);
for(ll x: ans) cout << x << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
5 ms |
1084 KB |
Output is correct |
6 |
Correct |
8 ms |
1236 KB |
Output is correct |
7 |
Correct |
6 ms |
1108 KB |
Output is correct |
8 |
Correct |
6 ms |
1108 KB |
Output is correct |
9 |
Correct |
6 ms |
1108 KB |
Output is correct |
10 |
Correct |
7 ms |
1108 KB |
Output is correct |
11 |
Correct |
7 ms |
1152 KB |
Output is correct |
12 |
Correct |
6 ms |
1236 KB |
Output is correct |
13 |
Correct |
6 ms |
1236 KB |
Output is correct |
14 |
Correct |
6 ms |
1236 KB |
Output is correct |
15 |
Correct |
6 ms |
1228 KB |
Output is correct |
16 |
Correct |
6 ms |
1208 KB |
Output is correct |
17 |
Correct |
6 ms |
1108 KB |
Output is correct |
18 |
Correct |
5 ms |
1240 KB |
Output is correct |
19 |
Correct |
5 ms |
1236 KB |
Output is correct |
20 |
Correct |
6 ms |
1228 KB |
Output is correct |
21 |
Correct |
5 ms |
1232 KB |
Output is correct |
22 |
Correct |
6 ms |
1236 KB |
Output is correct |
23 |
Correct |
6 ms |
1236 KB |
Output is correct |
24 |
Correct |
5 ms |
1236 KB |
Output is correct |
25 |
Correct |
6 ms |
1236 KB |
Output is correct |
26 |
Correct |
4 ms |
1192 KB |
Output is correct |
27 |
Correct |
4 ms |
1236 KB |
Output is correct |
28 |
Correct |
5 ms |
1236 KB |
Output is correct |
29 |
Correct |
5 ms |
1364 KB |
Output is correct |
30 |
Correct |
6 ms |
1188 KB |
Output is correct |
31 |
Correct |
7 ms |
1232 KB |
Output is correct |
32 |
Correct |
6 ms |
1236 KB |
Output is correct |
33 |
Correct |
6 ms |
1292 KB |
Output is correct |
34 |
Correct |
5 ms |
1236 KB |
Output is correct |
35 |
Correct |
5 ms |
1348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
6 ms |
1220 KB |
Output is correct |
3 |
Correct |
6 ms |
1108 KB |
Output is correct |
4 |
Correct |
5 ms |
1228 KB |
Output is correct |
5 |
Correct |
326 ms |
44376 KB |
Output is correct |
6 |
Correct |
365 ms |
42728 KB |
Output is correct |
7 |
Correct |
345 ms |
44984 KB |
Output is correct |
8 |
Correct |
288 ms |
40820 KB |
Output is correct |
9 |
Correct |
287 ms |
39768 KB |
Output is correct |
10 |
Correct |
461 ms |
44476 KB |
Output is correct |
11 |
Correct |
471 ms |
44476 KB |
Output is correct |
12 |
Correct |
484 ms |
44784 KB |
Output is correct |
13 |
Correct |
433 ms |
44684 KB |
Output is correct |
14 |
Correct |
455 ms |
44440 KB |
Output is correct |
15 |
Correct |
556 ms |
50956 KB |
Output is correct |
16 |
Correct |
494 ms |
51584 KB |
Output is correct |
17 |
Correct |
473 ms |
50456 KB |
Output is correct |
18 |
Correct |
533 ms |
43544 KB |
Output is correct |
19 |
Correct |
557 ms |
43664 KB |
Output is correct |
20 |
Correct |
562 ms |
43764 KB |
Output is correct |
21 |
Correct |
414 ms |
49960 KB |
Output is correct |
22 |
Correct |
440 ms |
50180 KB |
Output is correct |
23 |
Correct |
431 ms |
50108 KB |
Output is correct |
24 |
Correct |
436 ms |
50164 KB |
Output is correct |
25 |
Correct |
400 ms |
46548 KB |
Output is correct |
26 |
Correct |
384 ms |
47972 KB |
Output is correct |
27 |
Correct |
387 ms |
47340 KB |
Output is correct |
28 |
Correct |
267 ms |
47572 KB |
Output is correct |
29 |
Correct |
246 ms |
50876 KB |
Output is correct |
30 |
Correct |
391 ms |
47080 KB |
Output is correct |
31 |
Correct |
330 ms |
46816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
6 ms |
1228 KB |
Output is correct |
3 |
Correct |
6 ms |
1236 KB |
Output is correct |
4 |
Correct |
5 ms |
1264 KB |
Output is correct |
5 |
Correct |
267 ms |
49248 KB |
Output is correct |
6 |
Correct |
278 ms |
48708 KB |
Output is correct |
7 |
Correct |
338 ms |
41316 KB |
Output is correct |
8 |
Correct |
465 ms |
51432 KB |
Output is correct |
9 |
Correct |
445 ms |
51500 KB |
Output is correct |
10 |
Correct |
467 ms |
51572 KB |
Output is correct |
11 |
Correct |
370 ms |
51340 KB |
Output is correct |
12 |
Correct |
363 ms |
51528 KB |
Output is correct |
13 |
Correct |
364 ms |
51404 KB |
Output is correct |
14 |
Correct |
324 ms |
51564 KB |
Output is correct |
15 |
Correct |
307 ms |
51364 KB |
Output is correct |
16 |
Correct |
324 ms |
51596 KB |
Output is correct |
17 |
Correct |
310 ms |
51496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
5 ms |
1084 KB |
Output is correct |
6 |
Correct |
8 ms |
1236 KB |
Output is correct |
7 |
Correct |
6 ms |
1108 KB |
Output is correct |
8 |
Correct |
6 ms |
1108 KB |
Output is correct |
9 |
Correct |
6 ms |
1108 KB |
Output is correct |
10 |
Correct |
7 ms |
1108 KB |
Output is correct |
11 |
Correct |
7 ms |
1152 KB |
Output is correct |
12 |
Correct |
6 ms |
1236 KB |
Output is correct |
13 |
Correct |
6 ms |
1236 KB |
Output is correct |
14 |
Correct |
6 ms |
1236 KB |
Output is correct |
15 |
Correct |
6 ms |
1228 KB |
Output is correct |
16 |
Correct |
6 ms |
1208 KB |
Output is correct |
17 |
Correct |
6 ms |
1108 KB |
Output is correct |
18 |
Correct |
5 ms |
1240 KB |
Output is correct |
19 |
Correct |
5 ms |
1236 KB |
Output is correct |
20 |
Correct |
6 ms |
1228 KB |
Output is correct |
21 |
Correct |
5 ms |
1232 KB |
Output is correct |
22 |
Correct |
6 ms |
1236 KB |
Output is correct |
23 |
Correct |
6 ms |
1236 KB |
Output is correct |
24 |
Correct |
5 ms |
1236 KB |
Output is correct |
25 |
Correct |
6 ms |
1236 KB |
Output is correct |
26 |
Correct |
4 ms |
1192 KB |
Output is correct |
27 |
Correct |
4 ms |
1236 KB |
Output is correct |
28 |
Correct |
5 ms |
1236 KB |
Output is correct |
29 |
Correct |
5 ms |
1364 KB |
Output is correct |
30 |
Correct |
6 ms |
1188 KB |
Output is correct |
31 |
Correct |
7 ms |
1232 KB |
Output is correct |
32 |
Correct |
6 ms |
1236 KB |
Output is correct |
33 |
Correct |
6 ms |
1292 KB |
Output is correct |
34 |
Correct |
5 ms |
1236 KB |
Output is correct |
35 |
Correct |
5 ms |
1348 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
6 ms |
1220 KB |
Output is correct |
38 |
Correct |
6 ms |
1108 KB |
Output is correct |
39 |
Correct |
5 ms |
1228 KB |
Output is correct |
40 |
Correct |
326 ms |
44376 KB |
Output is correct |
41 |
Correct |
365 ms |
42728 KB |
Output is correct |
42 |
Correct |
345 ms |
44984 KB |
Output is correct |
43 |
Correct |
288 ms |
40820 KB |
Output is correct |
44 |
Correct |
287 ms |
39768 KB |
Output is correct |
45 |
Correct |
461 ms |
44476 KB |
Output is correct |
46 |
Correct |
471 ms |
44476 KB |
Output is correct |
47 |
Correct |
484 ms |
44784 KB |
Output is correct |
48 |
Correct |
433 ms |
44684 KB |
Output is correct |
49 |
Correct |
455 ms |
44440 KB |
Output is correct |
50 |
Correct |
556 ms |
50956 KB |
Output is correct |
51 |
Correct |
494 ms |
51584 KB |
Output is correct |
52 |
Correct |
473 ms |
50456 KB |
Output is correct |
53 |
Correct |
533 ms |
43544 KB |
Output is correct |
54 |
Correct |
557 ms |
43664 KB |
Output is correct |
55 |
Correct |
562 ms |
43764 KB |
Output is correct |
56 |
Correct |
414 ms |
49960 KB |
Output is correct |
57 |
Correct |
440 ms |
50180 KB |
Output is correct |
58 |
Correct |
431 ms |
50108 KB |
Output is correct |
59 |
Correct |
436 ms |
50164 KB |
Output is correct |
60 |
Correct |
400 ms |
46548 KB |
Output is correct |
61 |
Correct |
384 ms |
47972 KB |
Output is correct |
62 |
Correct |
387 ms |
47340 KB |
Output is correct |
63 |
Correct |
267 ms |
47572 KB |
Output is correct |
64 |
Correct |
246 ms |
50876 KB |
Output is correct |
65 |
Correct |
391 ms |
47080 KB |
Output is correct |
66 |
Correct |
330 ms |
46816 KB |
Output is correct |
67 |
Correct |
0 ms |
212 KB |
Output is correct |
68 |
Correct |
6 ms |
1228 KB |
Output is correct |
69 |
Correct |
6 ms |
1236 KB |
Output is correct |
70 |
Correct |
5 ms |
1264 KB |
Output is correct |
71 |
Correct |
267 ms |
49248 KB |
Output is correct |
72 |
Correct |
278 ms |
48708 KB |
Output is correct |
73 |
Correct |
338 ms |
41316 KB |
Output is correct |
74 |
Correct |
465 ms |
51432 KB |
Output is correct |
75 |
Correct |
445 ms |
51500 KB |
Output is correct |
76 |
Correct |
467 ms |
51572 KB |
Output is correct |
77 |
Correct |
370 ms |
51340 KB |
Output is correct |
78 |
Correct |
363 ms |
51528 KB |
Output is correct |
79 |
Correct |
364 ms |
51404 KB |
Output is correct |
80 |
Correct |
324 ms |
51564 KB |
Output is correct |
81 |
Correct |
307 ms |
51364 KB |
Output is correct |
82 |
Correct |
324 ms |
51596 KB |
Output is correct |
83 |
Correct |
310 ms |
51496 KB |
Output is correct |
84 |
Correct |
377 ms |
40356 KB |
Output is correct |
85 |
Correct |
327 ms |
34444 KB |
Output is correct |
86 |
Correct |
275 ms |
33500 KB |
Output is correct |
87 |
Correct |
479 ms |
44280 KB |
Output is correct |
88 |
Correct |
515 ms |
44520 KB |
Output is correct |
89 |
Correct |
500 ms |
44232 KB |
Output is correct |
90 |
Correct |
517 ms |
44304 KB |
Output is correct |
91 |
Correct |
500 ms |
44316 KB |
Output is correct |
92 |
Correct |
567 ms |
48456 KB |
Output is correct |
93 |
Correct |
517 ms |
50144 KB |
Output is correct |
94 |
Correct |
707 ms |
43512 KB |
Output is correct |
95 |
Correct |
729 ms |
43564 KB |
Output is correct |
96 |
Correct |
661 ms |
43536 KB |
Output is correct |
97 |
Correct |
618 ms |
43400 KB |
Output is correct |
98 |
Correct |
545 ms |
50004 KB |
Output is correct |
99 |
Correct |
480 ms |
49900 KB |
Output is correct |
100 |
Correct |
473 ms |
49920 KB |
Output is correct |
101 |
Correct |
504 ms |
50012 KB |
Output is correct |
102 |
Correct |
463 ms |
45408 KB |
Output is correct |
103 |
Correct |
531 ms |
45832 KB |
Output is correct |
104 |
Correct |
502 ms |
45648 KB |
Output is correct |
105 |
Correct |
300 ms |
46352 KB |
Output is correct |
106 |
Correct |
304 ms |
46728 KB |
Output is correct |
107 |
Correct |
411 ms |
46680 KB |
Output is correct |
108 |
Correct |
387 ms |
46644 KB |
Output is correct |