#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
const int MAX_N = 1e5+5;
const ll INF = 1e18;
int n, m, q, t, cnt;
int dep[MAX_N], anc[MAX_N][20], rt[MAX_N], ch[50*MAX_N][2];
ll sm[50*MAX_N], num[50*MAX_N];
vector<ll> nums[MAX_N];
vector<pii> adj[MAX_N];
int upd(int x, ll v, ll l = 0, ll r = 1e9){
ll x2 = ++cnt, m = (l+r)/2ll;
if(l == r){
sm[x2] = sm[x]+v;
num[x2] = num[x]+1;
return x2;
}
if(v <= m){
ch[x2][0] = upd(ch[x][0], v, l, m);
ch[x2][1] = ch[x][1];
} else{
ch[x2][0] = ch[x][0];
ch[x2][1] = upd(ch[x][1], v, m+1ll, r);
}
sm[x2] = sm[ch[x2][0]]+sm[ch[x2][1]];
num[x2] = num[ch[x2][0]]+num[ch[x2][1]];
return x2;
}
ll qry1(int x, ll ql, ll qr, ll l = 0, ll r = 1e9){
if(!x || ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return sm[x];
ll m = (l+r)/2ll;
return qry1(ch[x][0], ql, qr, l, m)+qry1(ch[x][1], ql, qr, m+1, r);
}
ll qry2(int x, ll ql, ll qr, ll l = 0, ll r = 1e9){
if(!x || ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return num[x];
ll m = (l+r)/2ll;
return qry2(ch[x][0], ql, qr, l, m)+qry2(ch[x][1], ql, qr, m+1, r);
}
void dfs(int curr, int par){
for(auto x : adj[curr]){
if(x.ff == par) continue;
dep[x.ff] = dep[curr]+1;
anc[x.ff][0] = curr;
rt[x.ff] = rt[curr];
for(auto y : nums[x.ss])
rt[x.ff] = upd(rt[x.ff], y);
dfs(x.ff, curr);
}
}
int lca(int a, int b){
if(dep[a] > dep[b]) swap(a, b);
F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b])
b = anc[b][i];
if(a == b) return a;
F0Rd(i, 20) if(anc[a][i] != anc[b][i])
a = anc[a][i], b = anc[b][i];
return anc[a][0];
}
pair<pii, ll> solve(int a, int b, ll x){ // number of things > x, number of things = x, sum of things < x
int c = lca(a, b);
pii y = {qry2(rt[a], x+1, 1e9)+qry2(rt[b], x+1, 1e9)-2ll*qry2(rt[c], x+1, 1e9), qry2(rt[a], x, x)+qry2(rt[b], x, x)-2ll*qry2(rt[c], x, x)};
pair<pii, ll> ans = {y, qry1(rt[a], 0, x-1ll)+qry1(rt[b], 0, x-1ll)-2ll*qry1(rt[c], 0, x-1ll)};
return ans;
}
int main(int argc, const char * argv[]){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> m >> q;
F0R(i, n-1){
int a, b; cin >> a >> b; a--, b--;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
F0R(i, m){
int a, b; cin >> a >> b; a--;
nums[a].push_back(b);
}
dfs(0, -1);
FOR(x, 1, 20) F0R(i, n)
anc[i][x] = anc[anc[i][x-1]][x-1];
F0R(i, q){
ll s, t, x, y; cin >> s >> t >> x >> y; s--, t--;
ll l = 0, r = min(y+1ll, (ll) 1e9);
while(l+1 < r){
ll mid = (l+r)/2ll;
if(solve(s, t, mid).ss <= y) l = mid;
else r = mid;
}
pair<pll, ll> z = solve(s, t, l);
pll ans = {z.ff.ff, z.ss};
if(z.ff.ss*l+z.ss <= y) ans.ss += z.ff.ss;
else ans.ss += l*((y-z.ss)/l), ans.ff += z.ff.ss-(y-z.ss)/l;
if(ans.ff > x) cout << "-1\n";
else cout << x-ans.ff << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
2 ms |
6744 KB |
Output is correct |
3 |
Correct |
2 ms |
7000 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
17 ms |
8028 KB |
Output is correct |
6 |
Correct |
26 ms |
8096 KB |
Output is correct |
7 |
Correct |
25 ms |
7768 KB |
Output is correct |
8 |
Correct |
30 ms |
8024 KB |
Output is correct |
9 |
Correct |
33 ms |
8024 KB |
Output is correct |
10 |
Correct |
38 ms |
8028 KB |
Output is correct |
11 |
Correct |
33 ms |
8024 KB |
Output is correct |
12 |
Correct |
32 ms |
8028 KB |
Output is correct |
13 |
Correct |
45 ms |
8308 KB |
Output is correct |
14 |
Correct |
43 ms |
8028 KB |
Output is correct |
15 |
Correct |
46 ms |
8220 KB |
Output is correct |
16 |
Correct |
46 ms |
8028 KB |
Output is correct |
17 |
Correct |
44 ms |
8028 KB |
Output is correct |
18 |
Correct |
44 ms |
8028 KB |
Output is correct |
19 |
Correct |
17 ms |
8028 KB |
Output is correct |
20 |
Correct |
17 ms |
8028 KB |
Output is correct |
21 |
Correct |
15 ms |
8064 KB |
Output is correct |
22 |
Correct |
18 ms |
8028 KB |
Output is correct |
23 |
Correct |
30 ms |
8024 KB |
Output is correct |
24 |
Correct |
31 ms |
8228 KB |
Output is correct |
25 |
Correct |
31 ms |
8280 KB |
Output is correct |
26 |
Correct |
27 ms |
8152 KB |
Output is correct |
27 |
Correct |
23 ms |
8028 KB |
Output is correct |
28 |
Correct |
24 ms |
8028 KB |
Output is correct |
29 |
Correct |
7 ms |
8028 KB |
Output is correct |
30 |
Correct |
40 ms |
8280 KB |
Output is correct |
31 |
Correct |
42 ms |
8028 KB |
Output is correct |
32 |
Correct |
32 ms |
8168 KB |
Output is correct |
33 |
Correct |
52 ms |
8468 KB |
Output is correct |
34 |
Correct |
53 ms |
8284 KB |
Output is correct |
35 |
Correct |
47 ms |
8284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
41 ms |
8108 KB |
Output is correct |
3 |
Correct |
42 ms |
8024 KB |
Output is correct |
4 |
Correct |
32 ms |
8168 KB |
Output is correct |
5 |
Correct |
1083 ms |
85676 KB |
Output is correct |
6 |
Correct |
1688 ms |
81156 KB |
Output is correct |
7 |
Correct |
1520 ms |
69412 KB |
Output is correct |
8 |
Correct |
1053 ms |
65300 KB |
Output is correct |
9 |
Correct |
1095 ms |
71984 KB |
Output is correct |
10 |
Correct |
2344 ms |
97996 KB |
Output is correct |
11 |
Correct |
2290 ms |
92056 KB |
Output is correct |
12 |
Correct |
2173 ms |
98248 KB |
Output is correct |
13 |
Correct |
2267 ms |
98132 KB |
Output is correct |
14 |
Correct |
2123 ms |
98520 KB |
Output is correct |
15 |
Correct |
2398 ms |
105040 KB |
Output is correct |
16 |
Correct |
2342 ms |
105420 KB |
Output is correct |
17 |
Correct |
2372 ms |
104636 KB |
Output is correct |
18 |
Correct |
2555 ms |
97972 KB |
Output is correct |
19 |
Correct |
2382 ms |
97796 KB |
Output is correct |
20 |
Correct |
2438 ms |
97916 KB |
Output is correct |
21 |
Correct |
1248 ms |
98248 KB |
Output is correct |
22 |
Correct |
1251 ms |
98532 KB |
Output is correct |
23 |
Correct |
782 ms |
98444 KB |
Output is correct |
24 |
Correct |
770 ms |
98228 KB |
Output is correct |
25 |
Correct |
2150 ms |
97928 KB |
Output is correct |
26 |
Correct |
2263 ms |
97632 KB |
Output is correct |
27 |
Correct |
2168 ms |
97704 KB |
Output is correct |
28 |
Correct |
2061 ms |
92192 KB |
Output is correct |
29 |
Correct |
1952 ms |
98288 KB |
Output is correct |
30 |
Correct |
2234 ms |
98368 KB |
Output is correct |
31 |
Correct |
2230 ms |
98420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
49 ms |
8224 KB |
Output is correct |
3 |
Correct |
47 ms |
8208 KB |
Output is correct |
4 |
Correct |
47 ms |
8028 KB |
Output is correct |
5 |
Correct |
2256 ms |
75724 KB |
Output is correct |
6 |
Correct |
2475 ms |
66688 KB |
Output is correct |
7 |
Correct |
3681 ms |
90808 KB |
Output is correct |
8 |
Correct |
4368 ms |
103792 KB |
Output is correct |
9 |
Correct |
4392 ms |
106672 KB |
Output is correct |
10 |
Correct |
4564 ms |
106576 KB |
Output is correct |
11 |
Correct |
3760 ms |
106456 KB |
Output is correct |
12 |
Correct |
3847 ms |
106220 KB |
Output is correct |
13 |
Correct |
3800 ms |
106264 KB |
Output is correct |
14 |
Correct |
2885 ms |
107032 KB |
Output is correct |
15 |
Correct |
3264 ms |
106696 KB |
Output is correct |
16 |
Correct |
3369 ms |
106840 KB |
Output is correct |
17 |
Correct |
3318 ms |
106556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
2 ms |
6744 KB |
Output is correct |
3 |
Correct |
2 ms |
7000 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
17 ms |
8028 KB |
Output is correct |
6 |
Correct |
26 ms |
8096 KB |
Output is correct |
7 |
Correct |
25 ms |
7768 KB |
Output is correct |
8 |
Correct |
30 ms |
8024 KB |
Output is correct |
9 |
Correct |
33 ms |
8024 KB |
Output is correct |
10 |
Correct |
38 ms |
8028 KB |
Output is correct |
11 |
Correct |
33 ms |
8024 KB |
Output is correct |
12 |
Correct |
32 ms |
8028 KB |
Output is correct |
13 |
Correct |
45 ms |
8308 KB |
Output is correct |
14 |
Correct |
43 ms |
8028 KB |
Output is correct |
15 |
Correct |
46 ms |
8220 KB |
Output is correct |
16 |
Correct |
46 ms |
8028 KB |
Output is correct |
17 |
Correct |
44 ms |
8028 KB |
Output is correct |
18 |
Correct |
44 ms |
8028 KB |
Output is correct |
19 |
Correct |
17 ms |
8028 KB |
Output is correct |
20 |
Correct |
17 ms |
8028 KB |
Output is correct |
21 |
Correct |
15 ms |
8064 KB |
Output is correct |
22 |
Correct |
18 ms |
8028 KB |
Output is correct |
23 |
Correct |
30 ms |
8024 KB |
Output is correct |
24 |
Correct |
31 ms |
8228 KB |
Output is correct |
25 |
Correct |
31 ms |
8280 KB |
Output is correct |
26 |
Correct |
27 ms |
8152 KB |
Output is correct |
27 |
Correct |
23 ms |
8028 KB |
Output is correct |
28 |
Correct |
24 ms |
8028 KB |
Output is correct |
29 |
Correct |
7 ms |
8028 KB |
Output is correct |
30 |
Correct |
40 ms |
8280 KB |
Output is correct |
31 |
Correct |
42 ms |
8028 KB |
Output is correct |
32 |
Correct |
32 ms |
8168 KB |
Output is correct |
33 |
Correct |
52 ms |
8468 KB |
Output is correct |
34 |
Correct |
53 ms |
8284 KB |
Output is correct |
35 |
Correct |
47 ms |
8284 KB |
Output is correct |
36 |
Correct |
1 ms |
6748 KB |
Output is correct |
37 |
Correct |
41 ms |
8108 KB |
Output is correct |
38 |
Correct |
42 ms |
8024 KB |
Output is correct |
39 |
Correct |
32 ms |
8168 KB |
Output is correct |
40 |
Correct |
1083 ms |
85676 KB |
Output is correct |
41 |
Correct |
1688 ms |
81156 KB |
Output is correct |
42 |
Correct |
1520 ms |
69412 KB |
Output is correct |
43 |
Correct |
1053 ms |
65300 KB |
Output is correct |
44 |
Correct |
1095 ms |
71984 KB |
Output is correct |
45 |
Correct |
2344 ms |
97996 KB |
Output is correct |
46 |
Correct |
2290 ms |
92056 KB |
Output is correct |
47 |
Correct |
2173 ms |
98248 KB |
Output is correct |
48 |
Correct |
2267 ms |
98132 KB |
Output is correct |
49 |
Correct |
2123 ms |
98520 KB |
Output is correct |
50 |
Correct |
2398 ms |
105040 KB |
Output is correct |
51 |
Correct |
2342 ms |
105420 KB |
Output is correct |
52 |
Correct |
2372 ms |
104636 KB |
Output is correct |
53 |
Correct |
2555 ms |
97972 KB |
Output is correct |
54 |
Correct |
2382 ms |
97796 KB |
Output is correct |
55 |
Correct |
2438 ms |
97916 KB |
Output is correct |
56 |
Correct |
1248 ms |
98248 KB |
Output is correct |
57 |
Correct |
1251 ms |
98532 KB |
Output is correct |
58 |
Correct |
782 ms |
98444 KB |
Output is correct |
59 |
Correct |
770 ms |
98228 KB |
Output is correct |
60 |
Correct |
2150 ms |
97928 KB |
Output is correct |
61 |
Correct |
2263 ms |
97632 KB |
Output is correct |
62 |
Correct |
2168 ms |
97704 KB |
Output is correct |
63 |
Correct |
2061 ms |
92192 KB |
Output is correct |
64 |
Correct |
1952 ms |
98288 KB |
Output is correct |
65 |
Correct |
2234 ms |
98368 KB |
Output is correct |
66 |
Correct |
2230 ms |
98420 KB |
Output is correct |
67 |
Correct |
2 ms |
6748 KB |
Output is correct |
68 |
Correct |
49 ms |
8224 KB |
Output is correct |
69 |
Correct |
47 ms |
8208 KB |
Output is correct |
70 |
Correct |
47 ms |
8028 KB |
Output is correct |
71 |
Correct |
2256 ms |
75724 KB |
Output is correct |
72 |
Correct |
2475 ms |
66688 KB |
Output is correct |
73 |
Correct |
3681 ms |
90808 KB |
Output is correct |
74 |
Correct |
4368 ms |
103792 KB |
Output is correct |
75 |
Correct |
4392 ms |
106672 KB |
Output is correct |
76 |
Correct |
4564 ms |
106576 KB |
Output is correct |
77 |
Correct |
3760 ms |
106456 KB |
Output is correct |
78 |
Correct |
3847 ms |
106220 KB |
Output is correct |
79 |
Correct |
3800 ms |
106264 KB |
Output is correct |
80 |
Correct |
2885 ms |
107032 KB |
Output is correct |
81 |
Correct |
3264 ms |
106696 KB |
Output is correct |
82 |
Correct |
3369 ms |
106840 KB |
Output is correct |
83 |
Correct |
3318 ms |
106556 KB |
Output is correct |
84 |
Correct |
1110 ms |
94532 KB |
Output is correct |
85 |
Correct |
1361 ms |
84412 KB |
Output is correct |
86 |
Correct |
1292 ms |
65356 KB |
Output is correct |
87 |
Correct |
1872 ms |
101492 KB |
Output is correct |
88 |
Correct |
1781 ms |
101388 KB |
Output is correct |
89 |
Correct |
1828 ms |
101276 KB |
Output is correct |
90 |
Correct |
1715 ms |
101036 KB |
Output is correct |
91 |
Correct |
1805 ms |
101036 KB |
Output is correct |
92 |
Correct |
3930 ms |
106260 KB |
Output is correct |
93 |
Correct |
4108 ms |
107964 KB |
Output is correct |
94 |
Correct |
3022 ms |
101364 KB |
Output is correct |
95 |
Correct |
3059 ms |
101568 KB |
Output is correct |
96 |
Correct |
3043 ms |
101408 KB |
Output is correct |
97 |
Correct |
3051 ms |
101332 KB |
Output is correct |
98 |
Correct |
735 ms |
100800 KB |
Output is correct |
99 |
Correct |
790 ms |
100784 KB |
Output is correct |
100 |
Correct |
865 ms |
101060 KB |
Output is correct |
101 |
Correct |
815 ms |
98956 KB |
Output is correct |
102 |
Correct |
1891 ms |
101284 KB |
Output is correct |
103 |
Correct |
1778 ms |
101496 KB |
Output is correct |
104 |
Correct |
1784 ms |
101308 KB |
Output is correct |
105 |
Correct |
1745 ms |
101316 KB |
Output is correct |
106 |
Correct |
1534 ms |
101076 KB |
Output is correct |
107 |
Correct |
1471 ms |
101228 KB |
Output is correct |
108 |
Correct |
1500 ms |
101400 KB |
Output is correct |