#include <bits/stdc++.h>
#define nosg "Two Currencies"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define maxn 200005
#define gb(i, j) ((i >> j) & 1)
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r) (rng);
}
int n, m, q;
pii edge[maxn], tram[maxn];
vector<int> o[maxn];
int cnt;
int in[maxn], out[maxn];
int h[maxn], cha[maxn][20];
void dfs(int u, int par)
{
in[u] = ++ cnt;
for(int v : o[u])
{
if(v == par) continue;
h[v] = h[u] + 1;
cha[v][0] = u;
fi(j, 1, 19) cha[v][j] = cha[cha[v][j - 1]][j - 1];
dfs(v, u);
}
out[u] = cnt;
}
int lca(int u, int v)
{
if(h[u] < h[v]) swap(u, v);
int kc = h[u] - h[v];
fi(j, 0, 19) if(gb(kc, j)) u = cha[u][j];
if(u == v) return u;
fid(j, 19, 0)
{
if(cha[u][j] != cha[v][j])
{
u = cha[u][j];
v = cha[v][j];
}
}
return cha[u][0];
}
const int maxs = 4000005;
int nNode;
int ver[maxs], L[maxs], R[maxs];
struct dl
{
ll v, sl;
} st[maxs], lazy[maxs];
int newleaf(int id, int l, int r, ll val1, ll val2)
{
int p = ++ nNode;
L[p] = L[id], R[p] = R[id];
st[p].v = st[id].v + 1ll * (r - l + 1) * val1;
st[p].sl = st[id].sl + 1ll * (r - l + 1) * val2;
lazy[p].v = lazy[id].v + val1;
lazy[p].sl = lazy[id].sl + val2;
return p;
}
void down(int id, int l, int r)
{
if(lazy[id].v)
{
if(l != r)
{
int mid = (l + r) >> 1;
L[id] = newleaf(L[id], l, mid, lazy[id].v, lazy[id].sl);
R[id] = newleaf(R[id], mid + 1, r, lazy[id].v, lazy[id].sl);
}
}
lazy[id].v = lazy[id].sl = 0;
}
int newparent(int lef, int rig)
{
int p = ++ nNode;
L[p] = lef, R[p] = rig;
st[p].v = st[L[p]].v + st[R[p]].v;
st[p].sl = st[L[p]].sl + st[R[p]].sl;
return p;
}
int update(int oid, int u, int v, ll val, int l = 1, int r = n)
{
if(v < l || r < u) return oid;
if(u <= l && r <= v) return newleaf(oid, l, r, val, 1ll);
down(oid, l, r);
int mid = (l + r) >> 1;
return newparent( update(L[oid], u, v, val, l, mid), update(R[oid], u, v, val, mid + 1, r) );
}
ll get(int id, int i, int l = 1, int r = n)
{
if(i < l || r < i) return 0;
if(l == r) return st[id].v;
down(id, l, r);
int mid = (l + r) >> 1;
return get(L[id], i, l, mid) + get(R[id], i, mid + 1, r);
}
ll get2(int id, int i, int l = 1, int r = n)
{
if(i < l || r < i) return 0;
if(l == r) return st[id].sl;
down(id, l, r);
int mid = (l + r) >> 1;
return get2(L[id], i, l, mid) + get2(R[id], i, mid + 1, r);
}
int main()
{
// freopen(nosg".inp","r",stdin);
// freopen(nosg".out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> q;
fi(i, 1, n - 1)
{
cin >> edge[i].f >> edge[i].s;
int u = edge[i].f, v = edge[i].s;
o[u].push_back(v);
o[v].push_back(u);
}
dfs(1, -1);
fi(i, 1, m) cin >> tram[i].f >> tram[i].s;
sort(tram + 1, tram + m + 1, [](pii x, pii y) {
return x.s < y.s;
});
fi(i, 1, m)
{
int j = tram[i].f, val = tram[i].s;
int u = edge[j].f, v = edge[j].s;
if(h[u] > h[v]) swap(u, v);
ver[i] = update(ver[i - 1], in[v], out[v], 1ll * val);
}
fi(i, 1, q)
{
int u, v;
ll S, G;
cin >> u >> v >> G >> S;
if(h[u] > h[v]) swap(u, v);
int par = lca(u, v);
int l = 1, r = m;
while(l <= r)
{
int mid = (l + r) >> 1;
if(get(ver[mid], in[v]) + get(ver[mid], in[u]) - 2ll * get(ver[mid], in[par]) <= S) l = mid + 1;
else r = mid - 1;
}
ll sum = get2(ver[m], in[v]) + get2(ver[m], in[u]) - 2ll * get2(ver[m], in[par]);
ll use = get2(ver[r], in[v]) + get2(ver[r], in[u]) - 2ll * get2(ver[r], in[par]);
cout << (G - (sum - use) >= 0 ? G - (sum - use) : -1) << '\n';
}
/// ------------------check time!-----------------///
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
10 2 1
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
2 4
5 3 2 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10592 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
12 ms |
14428 KB |
Output is correct |
6 |
Correct |
12 ms |
14684 KB |
Output is correct |
7 |
Correct |
11 ms |
15960 KB |
Output is correct |
8 |
Correct |
13 ms |
14680 KB |
Output is correct |
9 |
Correct |
14 ms |
15196 KB |
Output is correct |
10 |
Correct |
13 ms |
14684 KB |
Output is correct |
11 |
Correct |
18 ms |
15196 KB |
Output is correct |
12 |
Correct |
14 ms |
15192 KB |
Output is correct |
13 |
Correct |
24 ms |
27496 KB |
Output is correct |
14 |
Correct |
19 ms |
25448 KB |
Output is correct |
15 |
Correct |
18 ms |
25436 KB |
Output is correct |
16 |
Correct |
18 ms |
25272 KB |
Output is correct |
17 |
Correct |
17 ms |
23384 KB |
Output is correct |
18 |
Correct |
19 ms |
25432 KB |
Output is correct |
19 |
Correct |
18 ms |
14108 KB |
Output is correct |
20 |
Correct |
14 ms |
15708 KB |
Output is correct |
21 |
Correct |
17 ms |
11612 KB |
Output is correct |
22 |
Correct |
13 ms |
13916 KB |
Output is correct |
23 |
Correct |
14 ms |
14684 KB |
Output is correct |
24 |
Correct |
15 ms |
14168 KB |
Output is correct |
25 |
Correct |
12 ms |
14604 KB |
Output is correct |
26 |
Correct |
10 ms |
14172 KB |
Output is correct |
27 |
Correct |
10 ms |
14168 KB |
Output is correct |
28 |
Correct |
16 ms |
14444 KB |
Output is correct |
29 |
Correct |
10 ms |
14424 KB |
Output is correct |
30 |
Correct |
13 ms |
15196 KB |
Output is correct |
31 |
Correct |
13 ms |
16100 KB |
Output is correct |
32 |
Correct |
13 ms |
14168 KB |
Output is correct |
33 |
Correct |
18 ms |
27500 KB |
Output is correct |
34 |
Correct |
18 ms |
27484 KB |
Output is correct |
35 |
Correct |
18 ms |
27484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10588 KB |
Output is correct |
2 |
Correct |
17 ms |
15112 KB |
Output is correct |
3 |
Correct |
14 ms |
16220 KB |
Output is correct |
4 |
Correct |
13 ms |
14196 KB |
Output is correct |
5 |
Correct |
1655 ms |
151552 KB |
Output is correct |
6 |
Correct |
2572 ms |
156384 KB |
Output is correct |
7 |
Correct |
1993 ms |
119752 KB |
Output is correct |
8 |
Correct |
1449 ms |
113968 KB |
Output is correct |
9 |
Correct |
1426 ms |
134484 KB |
Output is correct |
10 |
Runtime error |
2153 ms |
361108 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
18 ms |
27676 KB |
Output is correct |
3 |
Correct |
18 ms |
27484 KB |
Output is correct |
4 |
Correct |
18 ms |
27484 KB |
Output is correct |
5 |
Runtime error |
364 ms |
378648 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10592 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
12 ms |
14428 KB |
Output is correct |
6 |
Correct |
12 ms |
14684 KB |
Output is correct |
7 |
Correct |
11 ms |
15960 KB |
Output is correct |
8 |
Correct |
13 ms |
14680 KB |
Output is correct |
9 |
Correct |
14 ms |
15196 KB |
Output is correct |
10 |
Correct |
13 ms |
14684 KB |
Output is correct |
11 |
Correct |
18 ms |
15196 KB |
Output is correct |
12 |
Correct |
14 ms |
15192 KB |
Output is correct |
13 |
Correct |
24 ms |
27496 KB |
Output is correct |
14 |
Correct |
19 ms |
25448 KB |
Output is correct |
15 |
Correct |
18 ms |
25436 KB |
Output is correct |
16 |
Correct |
18 ms |
25272 KB |
Output is correct |
17 |
Correct |
17 ms |
23384 KB |
Output is correct |
18 |
Correct |
19 ms |
25432 KB |
Output is correct |
19 |
Correct |
18 ms |
14108 KB |
Output is correct |
20 |
Correct |
14 ms |
15708 KB |
Output is correct |
21 |
Correct |
17 ms |
11612 KB |
Output is correct |
22 |
Correct |
13 ms |
13916 KB |
Output is correct |
23 |
Correct |
14 ms |
14684 KB |
Output is correct |
24 |
Correct |
15 ms |
14168 KB |
Output is correct |
25 |
Correct |
12 ms |
14604 KB |
Output is correct |
26 |
Correct |
10 ms |
14172 KB |
Output is correct |
27 |
Correct |
10 ms |
14168 KB |
Output is correct |
28 |
Correct |
16 ms |
14444 KB |
Output is correct |
29 |
Correct |
10 ms |
14424 KB |
Output is correct |
30 |
Correct |
13 ms |
15196 KB |
Output is correct |
31 |
Correct |
13 ms |
16100 KB |
Output is correct |
32 |
Correct |
13 ms |
14168 KB |
Output is correct |
33 |
Correct |
18 ms |
27500 KB |
Output is correct |
34 |
Correct |
18 ms |
27484 KB |
Output is correct |
35 |
Correct |
18 ms |
27484 KB |
Output is correct |
36 |
Correct |
3 ms |
10588 KB |
Output is correct |
37 |
Correct |
17 ms |
15112 KB |
Output is correct |
38 |
Correct |
14 ms |
16220 KB |
Output is correct |
39 |
Correct |
13 ms |
14196 KB |
Output is correct |
40 |
Correct |
1655 ms |
151552 KB |
Output is correct |
41 |
Correct |
2572 ms |
156384 KB |
Output is correct |
42 |
Correct |
1993 ms |
119752 KB |
Output is correct |
43 |
Correct |
1449 ms |
113968 KB |
Output is correct |
44 |
Correct |
1426 ms |
134484 KB |
Output is correct |
45 |
Runtime error |
2153 ms |
361108 KB |
Execution killed with signal 11 |
46 |
Halted |
0 ms |
0 KB |
- |