#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int pt = 0;
pair<ll,ll> tree[3*6000000];
int lft[3*6000000];
int rt[3*6000000];
int P[100005][30];
int root[100005];
vector<int> dep(100005);
vector<ll> w[100005];
vector<pair<int,int>> adj[100005];
int P2[100005][30];
void update(int node,int prv,int l,int r,ll idx,ll val){
if(l == r) return tree[node] = make_pair(tree[prv].first+l*val,tree[prv].second+val),void();
int md = l + r >> 1;
if(idx<=md){
int tmp = lft[prv];
lft[node] = ++pt;
rt[node] = rt[prv];
update(lft[node],tmp,l,md,idx,val);
}
else {
int tmp = rt[prv];
rt[node] = ++pt;
lft[node] = lft[prv];
update(rt[node],tmp,md+1,r,idx,val);
}
tree[node] = make_pair(tree[lft[node]].first+tree[rt[node]].first,tree[lft[node]].second+tree[rt[node]].second);
}
void update(int a,int b,ll val,ll frq){
if(!root[a]) root[a] = ++pt;
update(root[a],root[b],1,1e9,val,frq);
}
void dfs(int node,int par,int id){
P[node][0] = par;
P2[node][0] = w[id].size();
for(int k=1;k<30;k++) P[node][k] = P[P[node][k-1]][k-1],P2[node][k] = P2[node][k-1] + P2[P[node][k-1]][k-1];
for(auto e : adj[node]){
int ch = e.first;
if(ch == par) continue;
dep[ch] = dep[node] + 1;
update(ch,node,1,0);
for(auto ww : w[e.second]){
update(ch,ch,ww,1);
}
dfs(ch,node,e.second);
}
}
int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
if(a == b) return a;
for(int k=29;k>=0;k--){
if(dep[a]-(1<<k)>=dep[b]){
a = P[a][k];
}
}
if(a == b){
return a;
}
for(int i=29;i>=0;i--){
if(P[a][i]!=P[b][i]){
a = P[a][i];
b = P[b][i];
}
}
return P[a][0];
}
int calc(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
if(a == b) return a;
int ret = 0;
for(int k=29;k>=0;k--){
if(dep[a]-(1<<k)>=dep[b]){
ret += P2[a][k];
a = P[a][k];
}
}
if(a == b){
return ret;
}
for(int i=29;i>=0;i--){
if(P[a][i]!=P[b][i]){
ret += P2[a][i];
ret += P2[b][i];
a = P[a][i];
b = P[b][i];
}
}
ret += P2[a][0] + P2[b][0];
return ret;
}
ll query(int a,int b,int c,int l,int r,ll x){
if(l == r){
ll z = tree[a].second+tree[b].second-2*tree[c].second;
return min(x/(ll)l,z);
}
pair<ll,ll> sumOfL = make_pair(tree[lft[a]].first+tree[lft[b]].first-2LL*tree[lft[c]].first,tree[lft[a]].second+tree[lft[b]].second-2LL*tree[lft[c]].second);
pair<ll,ll> sumOfR = make_pair(tree[rt[a]].first+tree[rt[b]].first-2LL*tree[rt[c]].first,tree[rt[a]].second+tree[rt[b]].second-2LL*tree[rt[c]].second);
int md = l + r >> 1;
if(sumOfL.first>x) return query(lft[a],lft[b],lft[c],l,md,x);
return sumOfL.second + query(rt[a],rt[b],rt[c],md+1,r,x-sumOfL.first);
}
void solve(){
int n,m,q;
cin>>n>>m>>q;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
adj[a].push_back({b,i+1});
adj[b].push_back({a,i+1});
}
for(int i=0;i<m;i++){
ll a,b;
cin>>a>>b;
w[a].push_back(b);
}
dfs(1,0,0);/*
for(int i=1;i<=n;i++) {
cout<<tree[root[i]].first<<' ';
}
cout<<endl;*/
while(q--){
ll u,v,a,b;
cin>>u>>v>>a>>b;
ll z = query(root[u],root[v],root[lca(u,v)],1,1e9,b);
ll ans = a - (calc(u,v)-z);
cout<<(ans<0?-1:ans)<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
currencies.cpp: In function 'void update(int, int, int, int, ll, ll)':
currencies.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int md = l + r >> 1;
| ~~^~~
currencies.cpp: In function 'll query(int, int, int, int, int, ll)':
currencies.cpp:102:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | int md = l + r >> 1;
| ~~^~~
currencies.cpp:101:17: warning: variable 'sumOfR' set but not used [-Wunused-but-set-variable]
101 | pair<ll,ll> sumOfR = make_pair(tree[rt[a]].first+tree[rt[b]].first-2LL*tree[rt[c]].first,tree[rt[a]].second+tree[rt[b]].second-2LL*tree[rt[c]].second);
| ^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
2 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 ms |
5460 KB |
Output is correct |
4 |
Correct |
2 ms |
5460 KB |
Output is correct |
5 |
Correct |
7 ms |
8668 KB |
Output is correct |
6 |
Correct |
8 ms |
8740 KB |
Output is correct |
7 |
Correct |
6 ms |
7856 KB |
Output is correct |
8 |
Correct |
7 ms |
8916 KB |
Output is correct |
9 |
Correct |
8 ms |
8916 KB |
Output is correct |
10 |
Correct |
8 ms |
8952 KB |
Output is correct |
11 |
Correct |
8 ms |
8916 KB |
Output is correct |
12 |
Correct |
8 ms |
8928 KB |
Output is correct |
13 |
Correct |
8 ms |
9172 KB |
Output is correct |
14 |
Correct |
10 ms |
9036 KB |
Output is correct |
15 |
Correct |
8 ms |
9028 KB |
Output is correct |
16 |
Correct |
8 ms |
9036 KB |
Output is correct |
17 |
Correct |
9 ms |
9044 KB |
Output is correct |
18 |
Correct |
8 ms |
9032 KB |
Output is correct |
19 |
Correct |
10 ms |
8916 KB |
Output is correct |
20 |
Correct |
7 ms |
8944 KB |
Output is correct |
21 |
Correct |
7 ms |
8916 KB |
Output is correct |
22 |
Correct |
7 ms |
8916 KB |
Output is correct |
23 |
Correct |
7 ms |
8900 KB |
Output is correct |
24 |
Correct |
7 ms |
8904 KB |
Output is correct |
25 |
Correct |
10 ms |
8964 KB |
Output is correct |
26 |
Correct |
7 ms |
8916 KB |
Output is correct |
27 |
Correct |
7 ms |
8904 KB |
Output is correct |
28 |
Correct |
7 ms |
8916 KB |
Output is correct |
29 |
Correct |
7 ms |
8916 KB |
Output is correct |
30 |
Correct |
7 ms |
8916 KB |
Output is correct |
31 |
Correct |
7 ms |
8916 KB |
Output is correct |
32 |
Correct |
8 ms |
8900 KB |
Output is correct |
33 |
Correct |
8 ms |
9148 KB |
Output is correct |
34 |
Correct |
8 ms |
9172 KB |
Output is correct |
35 |
Correct |
8 ms |
9160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
9 ms |
8880 KB |
Output is correct |
3 |
Correct |
10 ms |
8916 KB |
Output is correct |
4 |
Correct |
9 ms |
8916 KB |
Output is correct |
5 |
Correct |
326 ms |
171152 KB |
Output is correct |
6 |
Correct |
319 ms |
136524 KB |
Output is correct |
7 |
Correct |
333 ms |
140104 KB |
Output is correct |
8 |
Correct |
328 ms |
141604 KB |
Output is correct |
9 |
Correct |
279 ms |
144864 KB |
Output is correct |
10 |
Correct |
390 ms |
183756 KB |
Output is correct |
11 |
Correct |
410 ms |
181532 KB |
Output is correct |
12 |
Correct |
406 ms |
183852 KB |
Output is correct |
13 |
Correct |
416 ms |
183924 KB |
Output is correct |
14 |
Correct |
400 ms |
183740 KB |
Output is correct |
15 |
Correct |
495 ms |
192576 KB |
Output is correct |
16 |
Correct |
549 ms |
193228 KB |
Output is correct |
17 |
Correct |
528 ms |
192120 KB |
Output is correct |
18 |
Correct |
462 ms |
183824 KB |
Output is correct |
19 |
Correct |
460 ms |
183716 KB |
Output is correct |
20 |
Correct |
482 ms |
183844 KB |
Output is correct |
21 |
Correct |
332 ms |
183348 KB |
Output is correct |
22 |
Correct |
332 ms |
183488 KB |
Output is correct |
23 |
Correct |
333 ms |
183524 KB |
Output is correct |
24 |
Correct |
333 ms |
183488 KB |
Output is correct |
25 |
Correct |
365 ms |
183736 KB |
Output is correct |
26 |
Correct |
346 ms |
183708 KB |
Output is correct |
27 |
Correct |
329 ms |
183676 KB |
Output is correct |
28 |
Correct |
259 ms |
181312 KB |
Output is correct |
29 |
Correct |
263 ms |
183628 KB |
Output is correct |
30 |
Correct |
293 ms |
183916 KB |
Output is correct |
31 |
Correct |
298 ms |
183832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
7 ms |
9044 KB |
Output is correct |
3 |
Correct |
10 ms |
9044 KB |
Output is correct |
4 |
Correct |
8 ms |
9044 KB |
Output is correct |
5 |
Correct |
396 ms |
157272 KB |
Output is correct |
6 |
Correct |
388 ms |
148412 KB |
Output is correct |
7 |
Correct |
518 ms |
136568 KB |
Output is correct |
8 |
Correct |
696 ms |
193212 KB |
Output is correct |
9 |
Correct |
671 ms |
193200 KB |
Output is correct |
10 |
Correct |
666 ms |
193152 KB |
Output is correct |
11 |
Correct |
626 ms |
192724 KB |
Output is correct |
12 |
Correct |
587 ms |
192696 KB |
Output is correct |
13 |
Correct |
603 ms |
192708 KB |
Output is correct |
14 |
Correct |
376 ms |
193076 KB |
Output is correct |
15 |
Correct |
363 ms |
192956 KB |
Output is correct |
16 |
Correct |
414 ms |
193192 KB |
Output is correct |
17 |
Correct |
430 ms |
193208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
2 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 ms |
5460 KB |
Output is correct |
4 |
Correct |
2 ms |
5460 KB |
Output is correct |
5 |
Correct |
7 ms |
8668 KB |
Output is correct |
6 |
Correct |
8 ms |
8740 KB |
Output is correct |
7 |
Correct |
6 ms |
7856 KB |
Output is correct |
8 |
Correct |
7 ms |
8916 KB |
Output is correct |
9 |
Correct |
8 ms |
8916 KB |
Output is correct |
10 |
Correct |
8 ms |
8952 KB |
Output is correct |
11 |
Correct |
8 ms |
8916 KB |
Output is correct |
12 |
Correct |
8 ms |
8928 KB |
Output is correct |
13 |
Correct |
8 ms |
9172 KB |
Output is correct |
14 |
Correct |
10 ms |
9036 KB |
Output is correct |
15 |
Correct |
8 ms |
9028 KB |
Output is correct |
16 |
Correct |
8 ms |
9036 KB |
Output is correct |
17 |
Correct |
9 ms |
9044 KB |
Output is correct |
18 |
Correct |
8 ms |
9032 KB |
Output is correct |
19 |
Correct |
10 ms |
8916 KB |
Output is correct |
20 |
Correct |
7 ms |
8944 KB |
Output is correct |
21 |
Correct |
7 ms |
8916 KB |
Output is correct |
22 |
Correct |
7 ms |
8916 KB |
Output is correct |
23 |
Correct |
7 ms |
8900 KB |
Output is correct |
24 |
Correct |
7 ms |
8904 KB |
Output is correct |
25 |
Correct |
10 ms |
8964 KB |
Output is correct |
26 |
Correct |
7 ms |
8916 KB |
Output is correct |
27 |
Correct |
7 ms |
8904 KB |
Output is correct |
28 |
Correct |
7 ms |
8916 KB |
Output is correct |
29 |
Correct |
7 ms |
8916 KB |
Output is correct |
30 |
Correct |
7 ms |
8916 KB |
Output is correct |
31 |
Correct |
7 ms |
8916 KB |
Output is correct |
32 |
Correct |
8 ms |
8900 KB |
Output is correct |
33 |
Correct |
8 ms |
9148 KB |
Output is correct |
34 |
Correct |
8 ms |
9172 KB |
Output is correct |
35 |
Correct |
8 ms |
9160 KB |
Output is correct |
36 |
Correct |
3 ms |
5460 KB |
Output is correct |
37 |
Correct |
9 ms |
8880 KB |
Output is correct |
38 |
Correct |
10 ms |
8916 KB |
Output is correct |
39 |
Correct |
9 ms |
8916 KB |
Output is correct |
40 |
Correct |
326 ms |
171152 KB |
Output is correct |
41 |
Correct |
319 ms |
136524 KB |
Output is correct |
42 |
Correct |
333 ms |
140104 KB |
Output is correct |
43 |
Correct |
328 ms |
141604 KB |
Output is correct |
44 |
Correct |
279 ms |
144864 KB |
Output is correct |
45 |
Correct |
390 ms |
183756 KB |
Output is correct |
46 |
Correct |
410 ms |
181532 KB |
Output is correct |
47 |
Correct |
406 ms |
183852 KB |
Output is correct |
48 |
Correct |
416 ms |
183924 KB |
Output is correct |
49 |
Correct |
400 ms |
183740 KB |
Output is correct |
50 |
Correct |
495 ms |
192576 KB |
Output is correct |
51 |
Correct |
549 ms |
193228 KB |
Output is correct |
52 |
Correct |
528 ms |
192120 KB |
Output is correct |
53 |
Correct |
462 ms |
183824 KB |
Output is correct |
54 |
Correct |
460 ms |
183716 KB |
Output is correct |
55 |
Correct |
482 ms |
183844 KB |
Output is correct |
56 |
Correct |
332 ms |
183348 KB |
Output is correct |
57 |
Correct |
332 ms |
183488 KB |
Output is correct |
58 |
Correct |
333 ms |
183524 KB |
Output is correct |
59 |
Correct |
333 ms |
183488 KB |
Output is correct |
60 |
Correct |
365 ms |
183736 KB |
Output is correct |
61 |
Correct |
346 ms |
183708 KB |
Output is correct |
62 |
Correct |
329 ms |
183676 KB |
Output is correct |
63 |
Correct |
259 ms |
181312 KB |
Output is correct |
64 |
Correct |
263 ms |
183628 KB |
Output is correct |
65 |
Correct |
293 ms |
183916 KB |
Output is correct |
66 |
Correct |
298 ms |
183832 KB |
Output is correct |
67 |
Correct |
3 ms |
5460 KB |
Output is correct |
68 |
Correct |
7 ms |
9044 KB |
Output is correct |
69 |
Correct |
10 ms |
9044 KB |
Output is correct |
70 |
Correct |
8 ms |
9044 KB |
Output is correct |
71 |
Correct |
396 ms |
157272 KB |
Output is correct |
72 |
Correct |
388 ms |
148412 KB |
Output is correct |
73 |
Correct |
518 ms |
136568 KB |
Output is correct |
74 |
Correct |
696 ms |
193212 KB |
Output is correct |
75 |
Correct |
671 ms |
193200 KB |
Output is correct |
76 |
Correct |
666 ms |
193152 KB |
Output is correct |
77 |
Correct |
626 ms |
192724 KB |
Output is correct |
78 |
Correct |
587 ms |
192696 KB |
Output is correct |
79 |
Correct |
603 ms |
192708 KB |
Output is correct |
80 |
Correct |
376 ms |
193076 KB |
Output is correct |
81 |
Correct |
363 ms |
192956 KB |
Output is correct |
82 |
Correct |
414 ms |
193192 KB |
Output is correct |
83 |
Correct |
430 ms |
193208 KB |
Output is correct |
84 |
Correct |
342 ms |
160884 KB |
Output is correct |
85 |
Correct |
299 ms |
124536 KB |
Output is correct |
86 |
Correct |
253 ms |
104500 KB |
Output is correct |
87 |
Correct |
449 ms |
183560 KB |
Output is correct |
88 |
Correct |
467 ms |
183572 KB |
Output is correct |
89 |
Correct |
443 ms |
183504 KB |
Output is correct |
90 |
Correct |
427 ms |
183572 KB |
Output is correct |
91 |
Correct |
455 ms |
183488 KB |
Output is correct |
92 |
Correct |
840 ms |
189580 KB |
Output is correct |
93 |
Correct |
778 ms |
191592 KB |
Output is correct |
94 |
Correct |
603 ms |
183692 KB |
Output is correct |
95 |
Correct |
578 ms |
183640 KB |
Output is correct |
96 |
Correct |
598 ms |
183624 KB |
Output is correct |
97 |
Correct |
602 ms |
183584 KB |
Output is correct |
98 |
Correct |
388 ms |
183292 KB |
Output is correct |
99 |
Correct |
365 ms |
183104 KB |
Output is correct |
100 |
Correct |
387 ms |
183440 KB |
Output is correct |
101 |
Correct |
369 ms |
183388 KB |
Output is correct |
102 |
Correct |
429 ms |
183588 KB |
Output is correct |
103 |
Correct |
421 ms |
183488 KB |
Output is correct |
104 |
Correct |
447 ms |
183488 KB |
Output is correct |
105 |
Correct |
333 ms |
183616 KB |
Output is correct |
106 |
Correct |
306 ms |
183540 KB |
Output is correct |
107 |
Correct |
317 ms |
183448 KB |
Output is correct |
108 |
Correct |
300 ms |
183528 KB |
Output is correct |