#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int Z = 1e5, INF = 1e18;
struct BIT {
int *a, n;
void init(int N) {
a = new int[(n = N) + 1] {};
}
void add(int i, int v) {
for(++i; i <= n; i += i&-i) a[i] += v;
}
int get(int i) {
int v = 0;
for(++i; i >= 1; i -= i&-i) v += a[i];
return v;
}
};
int N, M, Q, p[Z], lca[Z], eL[Z], eR[Z], dfsTimer, ans[Z];
vector<int> g[Z];
vector<array<int, 2>> o;
set<int> s[Z];
array<int, 4> q[Z];
BIT b[2] {};
void dfs0(int u) {
eL[u] = dfsTimer++;
for(int v : g[u]) if(v != p[u]) {
p[v] = u, dfs0(v);
if(size(s[v]) > size(s[u]))
swap(s[u], s[v]);
for(int i : s[v]) {
if(s[u].find(i) == end(s[u]))
s[u].insert(i);
else {
lca[i] = u;
s[u].erase(i);
}
}
}
eR[u] = dfsTimer++;
}
void add(int i, int u, int v) {
b[i].add(eL[u], +v);
b[i].add(eR[u], -v);
}
void modify(int i, int f) {
add(0, o[i][1], o[i][0] * f);
add(1, o[i][1], -f);
}
int calc(int i) {
array<int, 2> val;
for(int j : {0, 1})
val[j] = b[j].get(eL[q[i][0]]) + b[j].get(eL[q[i][1]]) - 2 * b[j].get(eL[lca[i]]);
if(val[0] <= q[i][3])
return q[i][2] - val[1];
else return -INF;
}
void dfs1(int l, int r, vector<int> &qry) {
if(r - l < 2 || empty(qry)) {
for(int i = l; i < r; ++i)
modify(i, +1);
for(int i : qry) ans[i] = calc(i);
if(!l && r == 1) {
modify(0, -1);
for(int i : qry) if(ans[i] == -INF)
ans[i] = calc(i);
modify(0, +1);
}
return;
}
int m = (l + r) / 2;
for(int i = l; i <= m; ++i) modify(i, +1);
vector<int> qv[2];
for(int i : qry)
qv[calc(i) > -INF].push_back(i);
for(int i = l; i <= m; ++i) modify(i, -1);
dfs1(l, m, qv[0]);
dfs1(m, r, qv[1]);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M >> Q;
array<int, 2> edges[N-1], temp[M];
for(auto &[u, v] : edges) {
cin >> u >> v; --u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
for(auto &[i, w] : temp)
cin >> i >> w, --i;
for(int i = 0; i < Q; ++i) {
cin >> q[i][0] >> q[i][1] >> q[i][2] >> q[i][3];
for(int j : {0, 1})
s[--q[i][j]].insert(i);
}
dfs0(0);
for(auto &[i, w] : temp) {
int u = edges[i][p[edges[i][1]] == edges[i][0]];
o.push_back({w, u});
}
for(int i : {0, 1})
b[i].init(2*N);
sort(begin(o), end(o));
for(auto [w, u] : o) add(1, u, 1);
vector<int> qv(Q);
iota(begin(qv), end(qv), 0);
dfs1(0, size(o), qv);
for(int i = 0; i < Q; ++i)
cout << max(ans[i], (int)-1) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7376 KB |
Output is correct |
5 |
Correct |
11 ms |
8100 KB |
Output is correct |
6 |
Correct |
16 ms |
8480 KB |
Output is correct |
7 |
Correct |
12 ms |
8268 KB |
Output is correct |
8 |
Correct |
14 ms |
8452 KB |
Output is correct |
9 |
Correct |
15 ms |
8392 KB |
Output is correct |
10 |
Correct |
15 ms |
8520 KB |
Output is correct |
11 |
Correct |
14 ms |
8516 KB |
Output is correct |
12 |
Correct |
15 ms |
8508 KB |
Output is correct |
13 |
Correct |
14 ms |
8368 KB |
Output is correct |
14 |
Correct |
13 ms |
8312 KB |
Output is correct |
15 |
Correct |
13 ms |
8336 KB |
Output is correct |
16 |
Correct |
17 ms |
8316 KB |
Output is correct |
17 |
Correct |
15 ms |
8368 KB |
Output is correct |
18 |
Correct |
14 ms |
8312 KB |
Output is correct |
19 |
Correct |
12 ms |
8096 KB |
Output is correct |
20 |
Correct |
12 ms |
8148 KB |
Output is correct |
21 |
Correct |
11 ms |
8212 KB |
Output is correct |
22 |
Correct |
15 ms |
8200 KB |
Output is correct |
23 |
Correct |
15 ms |
8364 KB |
Output is correct |
24 |
Correct |
12 ms |
8276 KB |
Output is correct |
25 |
Correct |
15 ms |
8276 KB |
Output is correct |
26 |
Correct |
10 ms |
8136 KB |
Output is correct |
27 |
Correct |
10 ms |
8136 KB |
Output is correct |
28 |
Correct |
11 ms |
8164 KB |
Output is correct |
29 |
Correct |
11 ms |
8212 KB |
Output is correct |
30 |
Correct |
16 ms |
8404 KB |
Output is correct |
31 |
Correct |
15 ms |
8472 KB |
Output is correct |
32 |
Correct |
16 ms |
8508 KB |
Output is correct |
33 |
Correct |
13 ms |
8352 KB |
Output is correct |
34 |
Correct |
14 ms |
8256 KB |
Output is correct |
35 |
Correct |
13 ms |
8324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
14 ms |
8496 KB |
Output is correct |
3 |
Correct |
14 ms |
8532 KB |
Output is correct |
4 |
Correct |
15 ms |
8404 KB |
Output is correct |
5 |
Correct |
751 ms |
60852 KB |
Output is correct |
6 |
Correct |
912 ms |
75820 KB |
Output is correct |
7 |
Correct |
836 ms |
75780 KB |
Output is correct |
8 |
Correct |
693 ms |
59744 KB |
Output is correct |
9 |
Correct |
650 ms |
56564 KB |
Output is correct |
10 |
Correct |
1010 ms |
78152 KB |
Output is correct |
11 |
Correct |
1006 ms |
78288 KB |
Output is correct |
12 |
Correct |
985 ms |
79104 KB |
Output is correct |
13 |
Correct |
1024 ms |
80300 KB |
Output is correct |
14 |
Correct |
1052 ms |
78916 KB |
Output is correct |
15 |
Correct |
989 ms |
57308 KB |
Output is correct |
16 |
Correct |
983 ms |
58208 KB |
Output is correct |
17 |
Correct |
1050 ms |
56780 KB |
Output is correct |
18 |
Correct |
948 ms |
65128 KB |
Output is correct |
19 |
Correct |
966 ms |
65912 KB |
Output is correct |
20 |
Correct |
965 ms |
64588 KB |
Output is correct |
21 |
Correct |
895 ms |
46688 KB |
Output is correct |
22 |
Correct |
950 ms |
46924 KB |
Output is correct |
23 |
Correct |
817 ms |
48872 KB |
Output is correct |
24 |
Correct |
788 ms |
48828 KB |
Output is correct |
25 |
Correct |
806 ms |
62676 KB |
Output is correct |
26 |
Correct |
827 ms |
64472 KB |
Output is correct |
27 |
Correct |
847 ms |
67568 KB |
Output is correct |
28 |
Correct |
530 ms |
45660 KB |
Output is correct |
29 |
Correct |
383 ms |
46684 KB |
Output is correct |
30 |
Correct |
568 ms |
47980 KB |
Output is correct |
31 |
Correct |
594 ms |
48064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7380 KB |
Output is correct |
2 |
Correct |
13 ms |
8348 KB |
Output is correct |
3 |
Correct |
13 ms |
8256 KB |
Output is correct |
4 |
Correct |
13 ms |
8276 KB |
Output is correct |
5 |
Correct |
497 ms |
48968 KB |
Output is correct |
6 |
Correct |
499 ms |
48912 KB |
Output is correct |
7 |
Correct |
713 ms |
46600 KB |
Output is correct |
8 |
Correct |
924 ms |
56936 KB |
Output is correct |
9 |
Correct |
905 ms |
56916 KB |
Output is correct |
10 |
Correct |
839 ms |
56720 KB |
Output is correct |
11 |
Correct |
801 ms |
58100 KB |
Output is correct |
12 |
Correct |
749 ms |
57640 KB |
Output is correct |
13 |
Correct |
708 ms |
57688 KB |
Output is correct |
14 |
Correct |
617 ms |
55916 KB |
Output is correct |
15 |
Correct |
569 ms |
56020 KB |
Output is correct |
16 |
Correct |
684 ms |
56344 KB |
Output is correct |
17 |
Correct |
678 ms |
56276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7376 KB |
Output is correct |
5 |
Correct |
11 ms |
8100 KB |
Output is correct |
6 |
Correct |
16 ms |
8480 KB |
Output is correct |
7 |
Correct |
12 ms |
8268 KB |
Output is correct |
8 |
Correct |
14 ms |
8452 KB |
Output is correct |
9 |
Correct |
15 ms |
8392 KB |
Output is correct |
10 |
Correct |
15 ms |
8520 KB |
Output is correct |
11 |
Correct |
14 ms |
8516 KB |
Output is correct |
12 |
Correct |
15 ms |
8508 KB |
Output is correct |
13 |
Correct |
14 ms |
8368 KB |
Output is correct |
14 |
Correct |
13 ms |
8312 KB |
Output is correct |
15 |
Correct |
13 ms |
8336 KB |
Output is correct |
16 |
Correct |
17 ms |
8316 KB |
Output is correct |
17 |
Correct |
15 ms |
8368 KB |
Output is correct |
18 |
Correct |
14 ms |
8312 KB |
Output is correct |
19 |
Correct |
12 ms |
8096 KB |
Output is correct |
20 |
Correct |
12 ms |
8148 KB |
Output is correct |
21 |
Correct |
11 ms |
8212 KB |
Output is correct |
22 |
Correct |
15 ms |
8200 KB |
Output is correct |
23 |
Correct |
15 ms |
8364 KB |
Output is correct |
24 |
Correct |
12 ms |
8276 KB |
Output is correct |
25 |
Correct |
15 ms |
8276 KB |
Output is correct |
26 |
Correct |
10 ms |
8136 KB |
Output is correct |
27 |
Correct |
10 ms |
8136 KB |
Output is correct |
28 |
Correct |
11 ms |
8164 KB |
Output is correct |
29 |
Correct |
11 ms |
8212 KB |
Output is correct |
30 |
Correct |
16 ms |
8404 KB |
Output is correct |
31 |
Correct |
15 ms |
8472 KB |
Output is correct |
32 |
Correct |
16 ms |
8508 KB |
Output is correct |
33 |
Correct |
13 ms |
8352 KB |
Output is correct |
34 |
Correct |
14 ms |
8256 KB |
Output is correct |
35 |
Correct |
13 ms |
8324 KB |
Output is correct |
36 |
Correct |
4 ms |
7380 KB |
Output is correct |
37 |
Correct |
14 ms |
8496 KB |
Output is correct |
38 |
Correct |
14 ms |
8532 KB |
Output is correct |
39 |
Correct |
15 ms |
8404 KB |
Output is correct |
40 |
Correct |
751 ms |
60852 KB |
Output is correct |
41 |
Correct |
912 ms |
75820 KB |
Output is correct |
42 |
Correct |
836 ms |
75780 KB |
Output is correct |
43 |
Correct |
693 ms |
59744 KB |
Output is correct |
44 |
Correct |
650 ms |
56564 KB |
Output is correct |
45 |
Correct |
1010 ms |
78152 KB |
Output is correct |
46 |
Correct |
1006 ms |
78288 KB |
Output is correct |
47 |
Correct |
985 ms |
79104 KB |
Output is correct |
48 |
Correct |
1024 ms |
80300 KB |
Output is correct |
49 |
Correct |
1052 ms |
78916 KB |
Output is correct |
50 |
Correct |
989 ms |
57308 KB |
Output is correct |
51 |
Correct |
983 ms |
58208 KB |
Output is correct |
52 |
Correct |
1050 ms |
56780 KB |
Output is correct |
53 |
Correct |
948 ms |
65128 KB |
Output is correct |
54 |
Correct |
966 ms |
65912 KB |
Output is correct |
55 |
Correct |
965 ms |
64588 KB |
Output is correct |
56 |
Correct |
895 ms |
46688 KB |
Output is correct |
57 |
Correct |
950 ms |
46924 KB |
Output is correct |
58 |
Correct |
817 ms |
48872 KB |
Output is correct |
59 |
Correct |
788 ms |
48828 KB |
Output is correct |
60 |
Correct |
806 ms |
62676 KB |
Output is correct |
61 |
Correct |
827 ms |
64472 KB |
Output is correct |
62 |
Correct |
847 ms |
67568 KB |
Output is correct |
63 |
Correct |
530 ms |
45660 KB |
Output is correct |
64 |
Correct |
383 ms |
46684 KB |
Output is correct |
65 |
Correct |
568 ms |
47980 KB |
Output is correct |
66 |
Correct |
594 ms |
48064 KB |
Output is correct |
67 |
Correct |
6 ms |
7380 KB |
Output is correct |
68 |
Correct |
13 ms |
8348 KB |
Output is correct |
69 |
Correct |
13 ms |
8256 KB |
Output is correct |
70 |
Correct |
13 ms |
8276 KB |
Output is correct |
71 |
Correct |
497 ms |
48968 KB |
Output is correct |
72 |
Correct |
499 ms |
48912 KB |
Output is correct |
73 |
Correct |
713 ms |
46600 KB |
Output is correct |
74 |
Correct |
924 ms |
56936 KB |
Output is correct |
75 |
Correct |
905 ms |
56916 KB |
Output is correct |
76 |
Correct |
839 ms |
56720 KB |
Output is correct |
77 |
Correct |
801 ms |
58100 KB |
Output is correct |
78 |
Correct |
749 ms |
57640 KB |
Output is correct |
79 |
Correct |
708 ms |
57688 KB |
Output is correct |
80 |
Correct |
617 ms |
55916 KB |
Output is correct |
81 |
Correct |
569 ms |
56020 KB |
Output is correct |
82 |
Correct |
684 ms |
56344 KB |
Output is correct |
83 |
Correct |
678 ms |
56276 KB |
Output is correct |
84 |
Correct |
720 ms |
59376 KB |
Output is correct |
85 |
Correct |
672 ms |
61252 KB |
Output is correct |
86 |
Correct |
596 ms |
61624 KB |
Output is correct |
87 |
Correct |
950 ms |
77848 KB |
Output is correct |
88 |
Correct |
1030 ms |
80476 KB |
Output is correct |
89 |
Correct |
998 ms |
78880 KB |
Output is correct |
90 |
Correct |
995 ms |
81072 KB |
Output is correct |
91 |
Correct |
1018 ms |
79900 KB |
Output is correct |
92 |
Correct |
925 ms |
53824 KB |
Output is correct |
93 |
Correct |
872 ms |
56464 KB |
Output is correct |
94 |
Correct |
1002 ms |
65476 KB |
Output is correct |
95 |
Correct |
980 ms |
64740 KB |
Output is correct |
96 |
Correct |
1044 ms |
65744 KB |
Output is correct |
97 |
Correct |
1000 ms |
66488 KB |
Output is correct |
98 |
Correct |
816 ms |
46984 KB |
Output is correct |
99 |
Correct |
849 ms |
46780 KB |
Output is correct |
100 |
Correct |
819 ms |
48784 KB |
Output is correct |
101 |
Correct |
865 ms |
48844 KB |
Output is correct |
102 |
Correct |
834 ms |
60008 KB |
Output is correct |
103 |
Correct |
777 ms |
60280 KB |
Output is correct |
104 |
Correct |
810 ms |
64644 KB |
Output is correct |
105 |
Correct |
541 ms |
44876 KB |
Output is correct |
106 |
Correct |
487 ms |
44676 KB |
Output is correct |
107 |
Correct |
644 ms |
46372 KB |
Output is correct |
108 |
Correct |
617 ms |
46412 KB |
Output is correct |