/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 20, MX = 30;
struct Node{
Node *L, *R;
ll sum;
int num;
Node(){
L = R = nullptr;
sum = num = 0;
}
Node(ll x, int nm){
L = R = nullptr;
sum = x;
num = nm;
}
Node(Node *l, Node *r){
L = l, R = r;
sum = L->sum + R->sum;
num = L->num + R->num;
}
void extend(){
if(L == nullptr) L = new Node();
if(R == nullptr) R = new Node();
}
};
int n, mi, q, s[N], tin[N], tout[N], up[N][K], heavy[N], dep[N], par[N], ESZ[N], ttin[N], toutt[N], timerr = 0;
ll sum[N];
vector<pair<int, int>> g[N], euler;
vector<int> E[N];
vector<Node*> roots;
Node* build(int l, int r){
if(l == r){
return new Node();
}
int m = l+r>>1;
return new Node(build(l, m), build(m+1, r));
}
Node *update(Node *v, int l, int r, int p, ll val){
if(l == r){
return new Node(val, val == 0 ? 0 : 1);
}
int m = l+r>>1;
if(p <= m){
return new Node(update(v->L, l, m, p, val), v->R);
}
return new Node(v->L, update(v->R, m+1, r, p, val));
}
int f(int l, int r, Node *u, Node *v, Node *uu, Node *vv, ll rsilver){
if(l == r){
ll val = v->sum - u->sum + vv->sum - uu->sum;
int nm = v->num - u->num + vv->num - uu->num;
// for(auto &pt: TV){
// val += pt.second->sum - pt.first->sum;
// nm += pt.second->num - pt.first->num;
// }
if(val <= rsilver) return nm;
return 0;
}
// cout << v->L->sum - u->L->sum + vv->L->sum - uu->L->sum << ' ' << l << ' ' << r << '|';
// cout << v->L->num - u->L->num + vv->L->num - uu->L->num << ' ' << l << ' ' << r << '\n';
int m = l+r>>1;
ll val = v->L->sum - u->L->sum + vv->L->sum - uu->L->sum;
int nm = v->L->num - u->L->num + vv->L->num - uu->L->num;
if(val <= rsilver){
// for(auto &pt: TV) pt.first = pt.first->R, pt.second = pt.second->R;
v = v->R;
vv = vv->R;
u = u->R;
uu = uu->R;
return nm + f(m+1, r, u, v, uu, vv, rsilver - val);
}
v = v->L;
vv = vv->L;
u = u->L;
uu = uu->L;
// for(auto &pt: TV) pt.first = pt.first->L, pt.second = pt.second->L;
return f(l, m, u, v, uu, vv, rsilver);
}
void dfs(int v, int p){
s[v] = 1;
par[v] = p;
dep[v] = dep[p] + 1;
for(auto &U: g[v]){
int u = U.first;
if(u != p){
sum[u] = sum[v];
for(auto x: E[U.second]) sum[u]++;
dfs(u, v);
up[u][0] = v;
s[v] += s[u];
if(s[u] > s[g[v][0].first] || g[v][0].first == p) swap(U, g[v][0]);
}
}
}
void dfs2(int v, int p, int &timer){
// tin[v] = timer - 1;
ttin[v] = timerr++;
// euler.
tin[v] = euler.size() + 1;
for(auto &U: g[v]){
int u = U.first;
if(u != p){
if(u == g[v][0].first) heavy[u] = heavy[v];
else heavy[u] = u;
timer += E[U.second].size();
ESZ[u] = E[U.second].size();
// tin[u] = euler.size() + 1;
vector<int> V;
for(auto x: E[U.second]){
euler.pb({x, euler.size() + 1});
V.pb(euler.size());
}
dfs2(u, v, timer);
int c = 0;
for(auto x: E[U.second]) euler.pb({x, -V[c++]});
// tout[u] = euler.size();
}
}
tout[v] = timer - 1;
toutt[v] = timerr++;
}
bool is_parent(int u, int v){
return ttin[u] <= ttin[v] && toutt[v] <= toutt[u];
}
int _lca(int u, int v){
if(is_parent(u, v)) return u;
if(is_parent(v, u)) return v;
for(int j = K-1; j >= 0 ; --j){
if(!is_parent(up[u][j], v)) u = up[u][j];
}
return up[u][0];
}
void solve(){
cin >> n >> mi >> q;
for(int i = 0; i < n - 1; ++i){
int u, v; cin >> u >> v;
g[u].pb({v, i+1});
g[v].pb({u, i+1});
}
for(int i = 0; i < mi; ++i){
int p, c; cin >> p >> c;
E[p].pb(c);
}
dep[1] = 1;
tin[1] = 1;
sum[1] = 0;
tout[1] = euler.size();
dfs(1, 1);
int tm = 1;
heavy[1] = 1;
dfs2(1, 1, tm);
up[1][0] = 1;
for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
vector<pair<int, int>> X = euler;
mi *= 2;
vector<int> pos(mi+1);
sort(all(X));
for(int i = 0; i < mi; ++i) pos[abs(X[i].second)] = i + 1;
roots.pb(build(1, mi));
for(int i = 1; i <= mi; ++i){
if(euler[i - 1].second > 0)
roots.pb(update(roots.back(), 1, mi, pos[i], euler[i - 1].first));
else
roots.pb(update(roots.back(), 1, mi, pos[-euler[i - 1].second], 0));
}
// for(int i = 1; i <= mi; ++i){
// cout << euler[i-1].first << ' ' << euler[i-1].second << '\n';
// }
// en;
// en;
// for(int i = 1; i <= n; ++i) cout << tin[i] << ' ';
// en;
// en;
// cout << roots[5]->sum - roots[2]->sum << ' ';
// for(auto x: X){
// cout << x.first << ' ' << x.second << '\n';
// }
// for(int i = 1; i <= n; ++i) cout << tin[i] << ' ' << tout[i] << '\n';
for(int i = 0; i < q; ++i){
int s, t; ll x, y; cin >> s >> t >> x >> y;
int lca = _lca(s, t);
// vector<pair<int, int>> T;
// if(lca != s){
// int v = s;
// while(v != lca){
// int next;
// if(dep[heavy[v]] <= dep[lca]){
// next = lca;
// if(tin[next] + 1 <= tin[v])
// T.pb({tin[next] + 1, tin[v]});
// break;
// }
// else{
// next = heavy[v];
// int L = tin[heavy[v]] - ESZ[heavy[v]] + 1;
// if(L <= tin[v])
// T.pb({L, tin[v]});
// }
// v = par[next];
// }
// }
// if(lca != t){
// int v = t;
// while(v != lca){
// int next;
// if(dep[heavy[v]] <= dep[lca]){
// next = lca;
// if(tin[next] + 1 <= tin[v])
// T.pb({tin[next] + 1, tin[v]});
// break;
// }
// else{
// next = heavy[v];
// int L = tin[heavy[v]] - ESZ[heavy[v]] + 1;
// if(L <= tin[v])
// T.pb({L, tin[v]});
// }
// v = par[next];
// }
// }
// cout << "q:";
// cout << s << ' ' << t << ' ' << lca << '\n';
// for(auto x:T) cout << x.first << ' ' << x.second << '\n';
// en;en;
int tot_gold = sum[s] + sum[t] - 2*sum[lca];
// cout << tot_gold << ' ';
// vector<pair<Node*, Node*>> TV;
// for(auto x: T){
// TV.pb({roots[x.first - 1], roots[x.second]});
// tot_gold += x.second - x.first + 1;
// }
// if(tin[s] > tin[t]) swap(s, t);
// cout << s << ' ' << t << ' ' << tin[s] - 1 << ' ' << tout[t] << '\n';
int rgold = x - (tot_gold - f(1, mi, roots[tin[lca] - 1], roots[tin[s] - 1], roots[tin[lca] - 1], roots[tin[t] - 1], y));
// cout << f(1, mi, roots[tin[lca] - 1], roots[tin[s] - 1], roots[tin[lca] - 1], roots[tin[t] - 1], y) << "f";
if(rgold < 0) cout << -1 << '\n';
else cout << rgold << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
currencies.cpp: In function 'Node* build(int, int)':
currencies.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int m = l+r>>1;
| ~^~
currencies.cpp: In function 'Node* update(Node*, int, int, int, long long int)':
currencies.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int m = l+r>>1;
| ~^~
currencies.cpp: In function 'int f(int, int, Node*, Node*, Node*, Node*, long long int)':
currencies.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m = l+r>>1;
| ~^~
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:106:16: warning: unused variable 'x' [-Wunused-variable]
106 | for(auto x: E[U.second]) sum[u]++;
| ^
currencies.cpp: In function 'int main()':
currencies.cpp:278:15: warning: unused variable 'aa' [-Wunused-variable]
278 | int tt = 1, aa;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66128 KB |
Output is correct |
2 |
Correct |
13 ms |
66140 KB |
Output is correct |
3 |
Correct |
13 ms |
66136 KB |
Output is correct |
4 |
Correct |
14 ms |
66140 KB |
Output is correct |
5 |
Correct |
17 ms |
69020 KB |
Output is correct |
6 |
Correct |
19 ms |
69212 KB |
Output is correct |
7 |
Correct |
17 ms |
68440 KB |
Output is correct |
8 |
Correct |
19 ms |
69212 KB |
Output is correct |
9 |
Correct |
19 ms |
69212 KB |
Output is correct |
10 |
Correct |
19 ms |
69276 KB |
Output is correct |
11 |
Correct |
19 ms |
69464 KB |
Output is correct |
12 |
Correct |
18 ms |
69212 KB |
Output is correct |
13 |
Correct |
19 ms |
69604 KB |
Output is correct |
14 |
Correct |
18 ms |
69468 KB |
Output is correct |
15 |
Correct |
20 ms |
69468 KB |
Output is correct |
16 |
Correct |
19 ms |
69440 KB |
Output is correct |
17 |
Correct |
21 ms |
69468 KB |
Output is correct |
18 |
Correct |
19 ms |
69464 KB |
Output is correct |
19 |
Correct |
18 ms |
69240 KB |
Output is correct |
20 |
Correct |
18 ms |
69212 KB |
Output is correct |
21 |
Correct |
19 ms |
69288 KB |
Output is correct |
22 |
Correct |
18 ms |
69212 KB |
Output is correct |
23 |
Correct |
19 ms |
69496 KB |
Output is correct |
24 |
Correct |
19 ms |
69268 KB |
Output is correct |
25 |
Correct |
18 ms |
69396 KB |
Output is correct |
26 |
Correct |
18 ms |
69464 KB |
Output is correct |
27 |
Correct |
18 ms |
69420 KB |
Output is correct |
28 |
Correct |
18 ms |
69468 KB |
Output is correct |
29 |
Correct |
18 ms |
69212 KB |
Output is correct |
30 |
Correct |
18 ms |
69212 KB |
Output is correct |
31 |
Correct |
19 ms |
69288 KB |
Output is correct |
32 |
Correct |
18 ms |
69212 KB |
Output is correct |
33 |
Correct |
18 ms |
69724 KB |
Output is correct |
34 |
Correct |
19 ms |
69724 KB |
Output is correct |
35 |
Correct |
20 ms |
69724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
66268 KB |
Output is correct |
2 |
Correct |
18 ms |
69212 KB |
Output is correct |
3 |
Correct |
18 ms |
69208 KB |
Output is correct |
4 |
Correct |
19 ms |
69212 KB |
Output is correct |
5 |
Correct |
349 ms |
263228 KB |
Output is correct |
6 |
Correct |
334 ms |
244152 KB |
Output is correct |
7 |
Correct |
309 ms |
212492 KB |
Output is correct |
8 |
Correct |
256 ms |
204264 KB |
Output is correct |
9 |
Correct |
265 ms |
215376 KB |
Output is correct |
10 |
Correct |
471 ms |
285892 KB |
Output is correct |
11 |
Correct |
442 ms |
285828 KB |
Output is correct |
12 |
Correct |
414 ms |
285888 KB |
Output is correct |
13 |
Correct |
447 ms |
285736 KB |
Output is correct |
14 |
Correct |
446 ms |
285884 KB |
Output is correct |
15 |
Correct |
489 ms |
301732 KB |
Output is correct |
16 |
Correct |
480 ms |
303000 KB |
Output is correct |
17 |
Correct |
485 ms |
301000 KB |
Output is correct |
18 |
Correct |
485 ms |
285996 KB |
Output is correct |
19 |
Correct |
476 ms |
286000 KB |
Output is correct |
20 |
Correct |
454 ms |
286096 KB |
Output is correct |
21 |
Correct |
397 ms |
285248 KB |
Output is correct |
22 |
Correct |
409 ms |
285424 KB |
Output is correct |
23 |
Correct |
402 ms |
285440 KB |
Output is correct |
24 |
Correct |
409 ms |
285584 KB |
Output is correct |
25 |
Correct |
401 ms |
285760 KB |
Output is correct |
26 |
Correct |
415 ms |
285796 KB |
Output is correct |
27 |
Correct |
421 ms |
285644 KB |
Output is correct |
28 |
Correct |
331 ms |
285708 KB |
Output is correct |
29 |
Correct |
307 ms |
285624 KB |
Output is correct |
30 |
Correct |
320 ms |
285888 KB |
Output is correct |
31 |
Correct |
325 ms |
285964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
66140 KB |
Output is correct |
2 |
Correct |
19 ms |
69552 KB |
Output is correct |
3 |
Correct |
18 ms |
69580 KB |
Output is correct |
4 |
Correct |
20 ms |
69724 KB |
Output is correct |
5 |
Correct |
379 ms |
225784 KB |
Output is correct |
6 |
Correct |
353 ms |
197972 KB |
Output is correct |
7 |
Correct |
569 ms |
274880 KB |
Output is correct |
8 |
Correct |
703 ms |
303312 KB |
Output is correct |
9 |
Correct |
673 ms |
303236 KB |
Output is correct |
10 |
Correct |
718 ms |
303304 KB |
Output is correct |
11 |
Correct |
621 ms |
302532 KB |
Output is correct |
12 |
Correct |
641 ms |
302652 KB |
Output is correct |
13 |
Correct |
626 ms |
302940 KB |
Output is correct |
14 |
Correct |
481 ms |
303040 KB |
Output is correct |
15 |
Correct |
505 ms |
302940 KB |
Output is correct |
16 |
Correct |
504 ms |
303272 KB |
Output is correct |
17 |
Correct |
528 ms |
303188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66128 KB |
Output is correct |
2 |
Correct |
13 ms |
66140 KB |
Output is correct |
3 |
Correct |
13 ms |
66136 KB |
Output is correct |
4 |
Correct |
14 ms |
66140 KB |
Output is correct |
5 |
Correct |
17 ms |
69020 KB |
Output is correct |
6 |
Correct |
19 ms |
69212 KB |
Output is correct |
7 |
Correct |
17 ms |
68440 KB |
Output is correct |
8 |
Correct |
19 ms |
69212 KB |
Output is correct |
9 |
Correct |
19 ms |
69212 KB |
Output is correct |
10 |
Correct |
19 ms |
69276 KB |
Output is correct |
11 |
Correct |
19 ms |
69464 KB |
Output is correct |
12 |
Correct |
18 ms |
69212 KB |
Output is correct |
13 |
Correct |
19 ms |
69604 KB |
Output is correct |
14 |
Correct |
18 ms |
69468 KB |
Output is correct |
15 |
Correct |
20 ms |
69468 KB |
Output is correct |
16 |
Correct |
19 ms |
69440 KB |
Output is correct |
17 |
Correct |
21 ms |
69468 KB |
Output is correct |
18 |
Correct |
19 ms |
69464 KB |
Output is correct |
19 |
Correct |
18 ms |
69240 KB |
Output is correct |
20 |
Correct |
18 ms |
69212 KB |
Output is correct |
21 |
Correct |
19 ms |
69288 KB |
Output is correct |
22 |
Correct |
18 ms |
69212 KB |
Output is correct |
23 |
Correct |
19 ms |
69496 KB |
Output is correct |
24 |
Correct |
19 ms |
69268 KB |
Output is correct |
25 |
Correct |
18 ms |
69396 KB |
Output is correct |
26 |
Correct |
18 ms |
69464 KB |
Output is correct |
27 |
Correct |
18 ms |
69420 KB |
Output is correct |
28 |
Correct |
18 ms |
69468 KB |
Output is correct |
29 |
Correct |
18 ms |
69212 KB |
Output is correct |
30 |
Correct |
18 ms |
69212 KB |
Output is correct |
31 |
Correct |
19 ms |
69288 KB |
Output is correct |
32 |
Correct |
18 ms |
69212 KB |
Output is correct |
33 |
Correct |
18 ms |
69724 KB |
Output is correct |
34 |
Correct |
19 ms |
69724 KB |
Output is correct |
35 |
Correct |
20 ms |
69724 KB |
Output is correct |
36 |
Correct |
14 ms |
66268 KB |
Output is correct |
37 |
Correct |
18 ms |
69212 KB |
Output is correct |
38 |
Correct |
18 ms |
69208 KB |
Output is correct |
39 |
Correct |
19 ms |
69212 KB |
Output is correct |
40 |
Correct |
349 ms |
263228 KB |
Output is correct |
41 |
Correct |
334 ms |
244152 KB |
Output is correct |
42 |
Correct |
309 ms |
212492 KB |
Output is correct |
43 |
Correct |
256 ms |
204264 KB |
Output is correct |
44 |
Correct |
265 ms |
215376 KB |
Output is correct |
45 |
Correct |
471 ms |
285892 KB |
Output is correct |
46 |
Correct |
442 ms |
285828 KB |
Output is correct |
47 |
Correct |
414 ms |
285888 KB |
Output is correct |
48 |
Correct |
447 ms |
285736 KB |
Output is correct |
49 |
Correct |
446 ms |
285884 KB |
Output is correct |
50 |
Correct |
489 ms |
301732 KB |
Output is correct |
51 |
Correct |
480 ms |
303000 KB |
Output is correct |
52 |
Correct |
485 ms |
301000 KB |
Output is correct |
53 |
Correct |
485 ms |
285996 KB |
Output is correct |
54 |
Correct |
476 ms |
286000 KB |
Output is correct |
55 |
Correct |
454 ms |
286096 KB |
Output is correct |
56 |
Correct |
397 ms |
285248 KB |
Output is correct |
57 |
Correct |
409 ms |
285424 KB |
Output is correct |
58 |
Correct |
402 ms |
285440 KB |
Output is correct |
59 |
Correct |
409 ms |
285584 KB |
Output is correct |
60 |
Correct |
401 ms |
285760 KB |
Output is correct |
61 |
Correct |
415 ms |
285796 KB |
Output is correct |
62 |
Correct |
421 ms |
285644 KB |
Output is correct |
63 |
Correct |
331 ms |
285708 KB |
Output is correct |
64 |
Correct |
307 ms |
285624 KB |
Output is correct |
65 |
Correct |
320 ms |
285888 KB |
Output is correct |
66 |
Correct |
325 ms |
285964 KB |
Output is correct |
67 |
Correct |
14 ms |
66140 KB |
Output is correct |
68 |
Correct |
19 ms |
69552 KB |
Output is correct |
69 |
Correct |
18 ms |
69580 KB |
Output is correct |
70 |
Correct |
20 ms |
69724 KB |
Output is correct |
71 |
Correct |
379 ms |
225784 KB |
Output is correct |
72 |
Correct |
353 ms |
197972 KB |
Output is correct |
73 |
Correct |
569 ms |
274880 KB |
Output is correct |
74 |
Correct |
703 ms |
303312 KB |
Output is correct |
75 |
Correct |
673 ms |
303236 KB |
Output is correct |
76 |
Correct |
718 ms |
303304 KB |
Output is correct |
77 |
Correct |
621 ms |
302532 KB |
Output is correct |
78 |
Correct |
641 ms |
302652 KB |
Output is correct |
79 |
Correct |
626 ms |
302940 KB |
Output is correct |
80 |
Correct |
481 ms |
303040 KB |
Output is correct |
81 |
Correct |
505 ms |
302940 KB |
Output is correct |
82 |
Correct |
504 ms |
303272 KB |
Output is correct |
83 |
Correct |
528 ms |
303188 KB |
Output is correct |
84 |
Correct |
464 ms |
269796 KB |
Output is correct |
85 |
Correct |
459 ms |
247964 KB |
Output is correct |
86 |
Correct |
342 ms |
192648 KB |
Output is correct |
87 |
Correct |
652 ms |
285656 KB |
Output is correct |
88 |
Correct |
665 ms |
286076 KB |
Output is correct |
89 |
Correct |
618 ms |
285696 KB |
Output is correct |
90 |
Correct |
634 ms |
285744 KB |
Output is correct |
91 |
Correct |
649 ms |
285708 KB |
Output is correct |
92 |
Correct |
769 ms |
296612 KB |
Output is correct |
93 |
Correct |
794 ms |
300496 KB |
Output is correct |
94 |
Correct |
692 ms |
286132 KB |
Output is correct |
95 |
Correct |
738 ms |
286156 KB |
Output is correct |
96 |
Correct |
715 ms |
285936 KB |
Output is correct |
97 |
Correct |
722 ms |
285952 KB |
Output is correct |
98 |
Correct |
603 ms |
285484 KB |
Output is correct |
99 |
Correct |
661 ms |
285512 KB |
Output is correct |
100 |
Correct |
614 ms |
285616 KB |
Output is correct |
101 |
Correct |
625 ms |
285488 KB |
Output is correct |
102 |
Correct |
623 ms |
285508 KB |
Output is correct |
103 |
Correct |
638 ms |
285544 KB |
Output is correct |
104 |
Correct |
688 ms |
285672 KB |
Output is correct |
105 |
Correct |
408 ms |
285848 KB |
Output is correct |
106 |
Correct |
401 ms |
285860 KB |
Output is correct |
107 |
Correct |
441 ms |
285632 KB |
Output is correct |
108 |
Correct |
418 ms |
285592 KB |
Output is correct |