#include <bits/stdc++.h>
#define fi first
#define se second
const int N = 100100;
using namespace std;
int n, m, q;
int dip[N];
int f[N][20];
int tin[N];
int tout[N];
int tim;
long long F[N], F2[N];
int A[N], B[N];
vector<int> v[N];
pair<int, int> cp[N];
int par[N];
long long s[N], t[N], x[N], y[N];
int tl[N], tr[N];
vector<int> qu[N];
int D[N];
void dfs(int x, int p)
{
tin[x] = ++tim;
f[x][0] = p;
for (int i = 1; i < 20; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i: v[x]) {
int y = A[i] ^ B[i] ^ x;
if (y == p) {
continue;
}
dip[y] = dip[x] + 1;
dfs(y, x);
}
tout[x] = tim;
}
bool isp(int x, int y)
{
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int x, int y)
{
if (isp(x, y)) {
return x;
} else if(isp(y, x)){
return y;
}
for (int i = 19; i >= 0; i--) {
if (!isp(f[x][i], y)) {
x = f[x][i];
}
}
return f[x][0];
}
void upd(int x, int y)
{
while (x < N) {
F[x] += y;
x += x & -x;
}
}
long long get(int x)
{
long long res = 0;
while (x > 0) {
res += F[x];
x -= x & -x;
}
return res;
}
void upd2(int x, int y)
{
while (x < N) {
F2[x] += y;
x += x & -x;
}
}
long long get2(int x)
{
long long res = 0;
while (x > 0) {
res += F2[x];
x -= x & -x;
}
return res;
}
int main()
{
#ifdef zxc
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
v[x].push_back(i);
v[y].push_back(i);
A[i] = x;
B[i] = y;
}
for (int i = 1; i <= m; i++) {
cin >> cp[i].se >> cp[i].fi;
}
sort(cp + 1, cp + m + 1);
for (int i = 1; i <= q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
tl[i] = 0;
tr[i] = m;
}
dfs(1, 1);
for (int i = 1; i < n; i++) {
if (dip[A[i]] > dip[B[i]]) {
swap(A[i], B[i]);
}
}
for (int i = 1; i <= q; i++) {
par[i] = lca(s[i], t[i]);
}
for (int it = 1; it <= 22; it++) {
for (int i = 1; i <= q; i++) {
int tm = (tl[i] + tr[i]) / 2 + (tl[i] < tr[i]);
//cout << tl[i] << " " << tr[i] << " " << tm << endl;
if (tl[i] <= tr[i]) {
qu[tm].push_back(i);
}
}
for (int i = 0; i <= m; i++) {
if (i > 0) {
int j = cp[i].se;
upd(tin[B[j]], cp[i].fi);
upd(tout[B[j]] + 1, -cp[i].fi);
upd2(tin[B[j]], 1);
upd2(tout[B[j]] + 1, -1);
}
for (int j: qu[i]) {
long long tot = get(tin[s[j]]) + get(tin[t[j]]) - 2 * get(tin[par[j]]);
long long col = get2(tin[s[j]]) + get2(tin[t[j]]) - 2 * get2(tin[par[j]]);
D[j] = col;
if (tot <= y[j]) {
tl[j] = i;
} else {
tr[j] = i - 1;
}
}
}
for (int i = 0; i < N; i++) {
F[i] = F2[i] = 0;
qu[i].clear();
}
}
for (int i = 1; i <= m; i++) {
int j = cp[i].se;
upd2(tin[B[j]], 1);
upd2(tout[B[j]] + 1, -1);
}
for (int i = 1; i <= q; i++) {
int golds = get2(tin[s[i]]) + get2(tin[t[i]]) - 2 * get2(tin[par[i]]);
//cout << golds << " " << D[i] << " " << tl[i] << " " << tr[i] << endl;
golds = x[i] - (golds - D[i]);
cout << max(golds, -1) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6612 KB |
Output is correct |
2 |
Correct |
5 ms |
6664 KB |
Output is correct |
3 |
Correct |
5 ms |
6612 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
11 ms |
6996 KB |
Output is correct |
6 |
Correct |
16 ms |
7164 KB |
Output is correct |
7 |
Correct |
12 ms |
7100 KB |
Output is correct |
8 |
Correct |
17 ms |
7164 KB |
Output is correct |
9 |
Correct |
13 ms |
7216 KB |
Output is correct |
10 |
Correct |
14 ms |
7252 KB |
Output is correct |
11 |
Correct |
15 ms |
7232 KB |
Output is correct |
12 |
Correct |
14 ms |
7252 KB |
Output is correct |
13 |
Correct |
13 ms |
7356 KB |
Output is correct |
14 |
Correct |
13 ms |
7252 KB |
Output is correct |
15 |
Correct |
15 ms |
7324 KB |
Output is correct |
16 |
Correct |
14 ms |
7252 KB |
Output is correct |
17 |
Correct |
15 ms |
7176 KB |
Output is correct |
18 |
Correct |
14 ms |
7296 KB |
Output is correct |
19 |
Correct |
13 ms |
7216 KB |
Output is correct |
20 |
Correct |
13 ms |
7228 KB |
Output is correct |
21 |
Correct |
13 ms |
7280 KB |
Output is correct |
22 |
Correct |
13 ms |
7224 KB |
Output is correct |
23 |
Correct |
13 ms |
7252 KB |
Output is correct |
24 |
Correct |
12 ms |
7280 KB |
Output is correct |
25 |
Correct |
16 ms |
7336 KB |
Output is correct |
26 |
Correct |
11 ms |
7252 KB |
Output is correct |
27 |
Correct |
12 ms |
7260 KB |
Output is correct |
28 |
Correct |
12 ms |
7232 KB |
Output is correct |
29 |
Correct |
13 ms |
7216 KB |
Output is correct |
30 |
Correct |
14 ms |
7228 KB |
Output is correct |
31 |
Correct |
16 ms |
7276 KB |
Output is correct |
32 |
Correct |
14 ms |
7252 KB |
Output is correct |
33 |
Correct |
13 ms |
7392 KB |
Output is correct |
34 |
Correct |
13 ms |
7316 KB |
Output is correct |
35 |
Correct |
13 ms |
7360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6612 KB |
Output is correct |
2 |
Correct |
13 ms |
7124 KB |
Output is correct |
3 |
Correct |
13 ms |
7252 KB |
Output is correct |
4 |
Correct |
13 ms |
7276 KB |
Output is correct |
5 |
Correct |
477 ms |
33532 KB |
Output is correct |
6 |
Correct |
446 ms |
34568 KB |
Output is correct |
7 |
Correct |
442 ms |
35108 KB |
Output is correct |
8 |
Correct |
382 ms |
31528 KB |
Output is correct |
9 |
Correct |
416 ms |
30836 KB |
Output is correct |
10 |
Correct |
571 ms |
40324 KB |
Output is correct |
11 |
Correct |
578 ms |
40432 KB |
Output is correct |
12 |
Correct |
562 ms |
40316 KB |
Output is correct |
13 |
Correct |
581 ms |
40184 KB |
Output is correct |
14 |
Correct |
537 ms |
40316 KB |
Output is correct |
15 |
Correct |
563 ms |
46924 KB |
Output is correct |
16 |
Correct |
534 ms |
47304 KB |
Output is correct |
17 |
Correct |
668 ms |
46536 KB |
Output is correct |
18 |
Correct |
628 ms |
40676 KB |
Output is correct |
19 |
Correct |
612 ms |
40688 KB |
Output is correct |
20 |
Correct |
627 ms |
40832 KB |
Output is correct |
21 |
Correct |
471 ms |
40520 KB |
Output is correct |
22 |
Correct |
462 ms |
40616 KB |
Output is correct |
23 |
Correct |
502 ms |
40704 KB |
Output is correct |
24 |
Correct |
474 ms |
40728 KB |
Output is correct |
25 |
Correct |
445 ms |
40416 KB |
Output is correct |
26 |
Correct |
468 ms |
40160 KB |
Output is correct |
27 |
Correct |
468 ms |
40336 KB |
Output is correct |
28 |
Correct |
354 ms |
38872 KB |
Output is correct |
29 |
Correct |
353 ms |
38312 KB |
Output is correct |
30 |
Correct |
393 ms |
38628 KB |
Output is correct |
31 |
Correct |
404 ms |
38704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6612 KB |
Output is correct |
2 |
Correct |
13 ms |
7252 KB |
Output is correct |
3 |
Correct |
16 ms |
7400 KB |
Output is correct |
4 |
Correct |
12 ms |
7320 KB |
Output is correct |
5 |
Correct |
384 ms |
39112 KB |
Output is correct |
6 |
Correct |
350 ms |
38728 KB |
Output is correct |
7 |
Correct |
493 ms |
35592 KB |
Output is correct |
8 |
Correct |
629 ms |
47424 KB |
Output is correct |
9 |
Correct |
671 ms |
47400 KB |
Output is correct |
10 |
Correct |
603 ms |
47500 KB |
Output is correct |
11 |
Correct |
478 ms |
47500 KB |
Output is correct |
12 |
Correct |
498 ms |
47424 KB |
Output is correct |
13 |
Correct |
525 ms |
47388 KB |
Output is correct |
14 |
Correct |
422 ms |
46756 KB |
Output is correct |
15 |
Correct |
397 ms |
46480 KB |
Output is correct |
16 |
Correct |
480 ms |
47084 KB |
Output is correct |
17 |
Correct |
451 ms |
46976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6612 KB |
Output is correct |
2 |
Correct |
5 ms |
6664 KB |
Output is correct |
3 |
Correct |
5 ms |
6612 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
11 ms |
6996 KB |
Output is correct |
6 |
Correct |
16 ms |
7164 KB |
Output is correct |
7 |
Correct |
12 ms |
7100 KB |
Output is correct |
8 |
Correct |
17 ms |
7164 KB |
Output is correct |
9 |
Correct |
13 ms |
7216 KB |
Output is correct |
10 |
Correct |
14 ms |
7252 KB |
Output is correct |
11 |
Correct |
15 ms |
7232 KB |
Output is correct |
12 |
Correct |
14 ms |
7252 KB |
Output is correct |
13 |
Correct |
13 ms |
7356 KB |
Output is correct |
14 |
Correct |
13 ms |
7252 KB |
Output is correct |
15 |
Correct |
15 ms |
7324 KB |
Output is correct |
16 |
Correct |
14 ms |
7252 KB |
Output is correct |
17 |
Correct |
15 ms |
7176 KB |
Output is correct |
18 |
Correct |
14 ms |
7296 KB |
Output is correct |
19 |
Correct |
13 ms |
7216 KB |
Output is correct |
20 |
Correct |
13 ms |
7228 KB |
Output is correct |
21 |
Correct |
13 ms |
7280 KB |
Output is correct |
22 |
Correct |
13 ms |
7224 KB |
Output is correct |
23 |
Correct |
13 ms |
7252 KB |
Output is correct |
24 |
Correct |
12 ms |
7280 KB |
Output is correct |
25 |
Correct |
16 ms |
7336 KB |
Output is correct |
26 |
Correct |
11 ms |
7252 KB |
Output is correct |
27 |
Correct |
12 ms |
7260 KB |
Output is correct |
28 |
Correct |
12 ms |
7232 KB |
Output is correct |
29 |
Correct |
13 ms |
7216 KB |
Output is correct |
30 |
Correct |
14 ms |
7228 KB |
Output is correct |
31 |
Correct |
16 ms |
7276 KB |
Output is correct |
32 |
Correct |
14 ms |
7252 KB |
Output is correct |
33 |
Correct |
13 ms |
7392 KB |
Output is correct |
34 |
Correct |
13 ms |
7316 KB |
Output is correct |
35 |
Correct |
13 ms |
7360 KB |
Output is correct |
36 |
Correct |
5 ms |
6612 KB |
Output is correct |
37 |
Correct |
13 ms |
7124 KB |
Output is correct |
38 |
Correct |
13 ms |
7252 KB |
Output is correct |
39 |
Correct |
13 ms |
7276 KB |
Output is correct |
40 |
Correct |
477 ms |
33532 KB |
Output is correct |
41 |
Correct |
446 ms |
34568 KB |
Output is correct |
42 |
Correct |
442 ms |
35108 KB |
Output is correct |
43 |
Correct |
382 ms |
31528 KB |
Output is correct |
44 |
Correct |
416 ms |
30836 KB |
Output is correct |
45 |
Correct |
571 ms |
40324 KB |
Output is correct |
46 |
Correct |
578 ms |
40432 KB |
Output is correct |
47 |
Correct |
562 ms |
40316 KB |
Output is correct |
48 |
Correct |
581 ms |
40184 KB |
Output is correct |
49 |
Correct |
537 ms |
40316 KB |
Output is correct |
50 |
Correct |
563 ms |
46924 KB |
Output is correct |
51 |
Correct |
534 ms |
47304 KB |
Output is correct |
52 |
Correct |
668 ms |
46536 KB |
Output is correct |
53 |
Correct |
628 ms |
40676 KB |
Output is correct |
54 |
Correct |
612 ms |
40688 KB |
Output is correct |
55 |
Correct |
627 ms |
40832 KB |
Output is correct |
56 |
Correct |
471 ms |
40520 KB |
Output is correct |
57 |
Correct |
462 ms |
40616 KB |
Output is correct |
58 |
Correct |
502 ms |
40704 KB |
Output is correct |
59 |
Correct |
474 ms |
40728 KB |
Output is correct |
60 |
Correct |
445 ms |
40416 KB |
Output is correct |
61 |
Correct |
468 ms |
40160 KB |
Output is correct |
62 |
Correct |
468 ms |
40336 KB |
Output is correct |
63 |
Correct |
354 ms |
38872 KB |
Output is correct |
64 |
Correct |
353 ms |
38312 KB |
Output is correct |
65 |
Correct |
393 ms |
38628 KB |
Output is correct |
66 |
Correct |
404 ms |
38704 KB |
Output is correct |
67 |
Correct |
5 ms |
6612 KB |
Output is correct |
68 |
Correct |
13 ms |
7252 KB |
Output is correct |
69 |
Correct |
16 ms |
7400 KB |
Output is correct |
70 |
Correct |
12 ms |
7320 KB |
Output is correct |
71 |
Correct |
384 ms |
39112 KB |
Output is correct |
72 |
Correct |
350 ms |
38728 KB |
Output is correct |
73 |
Correct |
493 ms |
35592 KB |
Output is correct |
74 |
Correct |
629 ms |
47424 KB |
Output is correct |
75 |
Correct |
671 ms |
47400 KB |
Output is correct |
76 |
Correct |
603 ms |
47500 KB |
Output is correct |
77 |
Correct |
478 ms |
47500 KB |
Output is correct |
78 |
Correct |
498 ms |
47424 KB |
Output is correct |
79 |
Correct |
525 ms |
47388 KB |
Output is correct |
80 |
Correct |
422 ms |
46756 KB |
Output is correct |
81 |
Correct |
397 ms |
46480 KB |
Output is correct |
82 |
Correct |
480 ms |
47084 KB |
Output is correct |
83 |
Correct |
451 ms |
46976 KB |
Output is correct |
84 |
Correct |
425 ms |
31780 KB |
Output is correct |
85 |
Correct |
481 ms |
29392 KB |
Output is correct |
86 |
Correct |
366 ms |
28548 KB |
Output is correct |
87 |
Correct |
639 ms |
40396 KB |
Output is correct |
88 |
Correct |
622 ms |
40272 KB |
Output is correct |
89 |
Correct |
712 ms |
40272 KB |
Output is correct |
90 |
Correct |
622 ms |
40268 KB |
Output is correct |
91 |
Correct |
633 ms |
40364 KB |
Output is correct |
92 |
Correct |
721 ms |
45128 KB |
Output is correct |
93 |
Correct |
617 ms |
46372 KB |
Output is correct |
94 |
Correct |
667 ms |
40724 KB |
Output is correct |
95 |
Correct |
675 ms |
40760 KB |
Output is correct |
96 |
Correct |
720 ms |
40828 KB |
Output is correct |
97 |
Correct |
664 ms |
40792 KB |
Output is correct |
98 |
Correct |
534 ms |
40592 KB |
Output is correct |
99 |
Correct |
573 ms |
40204 KB |
Output is correct |
100 |
Correct |
544 ms |
40468 KB |
Output is correct |
101 |
Correct |
592 ms |
40564 KB |
Output is correct |
102 |
Correct |
556 ms |
40944 KB |
Output is correct |
103 |
Correct |
555 ms |
40916 KB |
Output is correct |
104 |
Correct |
508 ms |
40864 KB |
Output is correct |
105 |
Correct |
482 ms |
38112 KB |
Output is correct |
106 |
Correct |
440 ms |
39160 KB |
Output is correct |
107 |
Correct |
426 ms |
38252 KB |
Output is correct |
108 |
Correct |
446 ms |
38400 KB |
Output is correct |