#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>
const ll MAXN = 1e5 + 5;
const ll INF = 2e12;
map<ll,ll> scal;
map<ll,ll> wtyl;
ll cnt = 1;
struct Node{
ll suma;
ll ilosc;
Node *l, *r;
Node(ll x, ll y) : suma(x), ilosc(y) {};
Node(Node *ll, Node *rr) : suma(ll->suma + rr->suma), ilosc(ll->ilosc + rr->ilosc), l(ll), r(rr) {};
};
vector<pair<ll, vector<ll>>> graf[MAXN];
ll gl[MAXN];
ll ile[MAXN];
ll przodek[MAXN][17];
Node *roots[MAXN];
struct d{
ll a;
ll b;
vector<ll> koszty;
};
vector<d> kraw;
const ll base = 1 << 17;
Node *build(ll akt_a = 1, ll akt_b = base){
if(akt_a == akt_b) return new Node(0ll, 0ll);
ll mid = (akt_a + akt_b) / 2;
return new Node(build(akt_a, mid), build(mid + 1, akt_b));
}
Node *dodaj(Node *w, ll ind, ll akt_a = 1, ll akt_b = base){
if(akt_a == akt_b){
return new Node(w->suma + wtyl[ind], w->ilosc + 1);
}
ll mid = (akt_a + akt_b) / 2;
if(ind <= mid){
return new Node(dodaj(w->l, ind, akt_a, mid), w->r);
}
else{
return new Node(w->l, dodaj(w->r, ind, mid + 1, akt_b));
}
}
set<ll> koszty;
ll ktory[MAXN];
ll it = 2;
void dfs(ll v, ll p){
for(auto u : graf[v]){
if(u.first == p) continue;
gl[u.first] = gl[v] + 1;
przodek[u.first][0] = v;
ile[u.first] = ile[v] + u.second.size();
for(ll j = 1; j < 17; ++j){
przodek[u.first][j] = przodek[przodek[u.first][j-1]][j-1];
}
if(u.second.size() == 0) ktory[u.first] = ktory[v];
for(ll j = 0; j < u.second.size(); ++j){
if(j == 0){
roots[it] = dodaj(roots[ktory[v]], u.second[j], 1, base);
ktory[u.first] = it;
++it;
}
else{
roots[it] = dodaj(roots[ktory[u.first]], u.second[j], 1, base);
ktory[u.first] = it;
++it;
}
}
dfs(u.first, v);
}
}
ll LCA(ll x, ll y){
if(x == y) return x;
if(gl[x] < gl[y]) swap(x, y);
for(ll j = 16; j >= 0; --j){
if(gl[x] - (1 << j) >= gl[y]){
x = przodek[x][j];
}
}
if(x == y) return x;
for(ll j = 16; j >= 0; --j){
if(gl[x] >= (1 << j) and przodek[x][j] != przodek[y][j]){
x = przodek[x][j];
y = przodek[y][j];
}
}
return przodek[x][0];
}
ll obl(Node *a, Node *b, Node *x, ll suma, ll akt_a, ll akt_b, ll currsuma){
if(akt_a == akt_b){
ll S = a->suma + b->suma - 2 * x->suma;
ll L = a->ilosc + b->ilosc - 2 * x->ilosc;
if(S == 0 or L == 0) return 0;
else return min(L, (suma - currsuma) / (S / L));
}
ll mid = (akt_a + akt_b) / 2;
ll lewasuma = a->l->suma + b->l->suma - 2 * x->l->suma;
ll lewailosc = a->l->ilosc + b->l->ilosc - 2 * x->l->ilosc;
if(currsuma + lewasuma < suma){
return obl(a->r, b->r, x->r, suma, mid + 1, akt_b, currsuma + lewasuma) + lewailosc;
}
else{
return obl(a->l, b->l, x->l, suma, akt_a, mid, currsuma);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, m, q;
cin >> n >> m >> q;
ll a, b;
for(ll i = 0; i < n-1; ++i){
cin >> a >> b;
kraw.push_back({a, b});
}
for(ll i = 0; i < m; ++i){
cin >> a >> b;
kraw[a-1].koszty.push_back(b);
koszty.insert(b);
}
for(auto u : koszty){
scal[u] = cnt;
wtyl[cnt] = u;
++cnt;
}
for(auto &u : kraw){
graf[u.a].push_back({u.b, {}});
graf[u.b].push_back({u.a, {}});
for(auto &t : u.koszty){
t = scal[t];
graf[u.a].back().second.push_back(t);
graf[u.b].back().second.push_back(t);
}
}
roots[1] = build();
ktory[1] = 1;
dfs(1, 0);
ll c, d;
for(ll i = 0; i < q; ++i){
cin >> a >> b >> c >> d;
ll x = LCA(a, b);
ll ans = c - (ile[a] + ile[b] - 2 * ile[x] - obl(roots[ktory[a]], roots[ktory[b]], roots[ktory[x]], d, 1, base, 0));
if(ans < 0) cout << -1 << "\n";
else cout << ans << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |