#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
int n, m, q;
vector<vector<pair<int, int>>> g;
vector<pair<int, int>> ogE;
vector<int> subS, inEu, eu, over;
vector<ll> qAvail, qAvail2, dep, answers;
vector<vector<int>> costs;
map<ll, int> edges;
int pret;
vector<bool> off;
int tB;
vector<ll> ts, t1;
int squirt;
void tAdd(int i, ll x, ll times) {
i += tB;
if(x < 0) x *= -1, times *= -1;
DC << " tAdd(" << i - tB << ' ' << x << ' ' << times << ")" << eol;
ts[i] += x * times;
t1[i] += times;
while(i) i /= 2, ts[i] = ts[2 * i] + ts[2 * i + 1], t1[i] = t1[2 * i] + t1[2 * i + 1];
}
ll tQ(ll x) {
int v = 1;
ll ans = 0;
while(v < tB) {
v *= 2;
if(ts[v] <= x) ans += t1[v], x -= ts[v], v++;
}
if(t1[v] && ts[v]) {
ll base = ts[v] / t1[v];
ans += min(x / base, t1[v]);
}
if(!ts[v]) ans += t1[v];
return ans;
}
void dfs1(int v, int p) {
subS[v] = 1;
repIn2(u, c, g[v]) if(u != p && !off[u]) dfs1(u, v), subS[v] += subS[u], edges[c] = 1;
}
void dfs2(int v, int p, int cen, int ove) {
subS[v] = 1;
inEu[v] = pret;
eu[pret++] = v;
over[v] = ove;
repIn2(u, c, g[v]) if(u != p && !off[u]) dep[u] = dep[v] + c, dfs2(u, v, cen, (v == cen ? u : ove)), subS[v] += subS[u], eu[pret++] = v;
}
bool mosCmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
auto [al, ar] = a.first;
auto [bl, br] = b.first;
if(al / squirt == bl / squirt) return ((al / squirt) % 2) ? ar < br : ar > br;
return al < bl;
}
void decompose(int v, vector<pair<pair<int, int>, int>>& queries) {
edges.clear();
dfs1(v, 0);
edges.erase(0);
int cen = v;
bool found = false;
while(!found) {
found = true;
repIn2(u, c, g[cen]) if(!off[u] && subS[u] * 2 > subS[v] && subS[u] < subS[cen]) { cen = u, found = false; break; }
}
v = cen;
off[cen] = true;
pret=0;
dep[v] = 0;
dfs2(v, 0, v, 0);
vector<pair<pair<int, int>, int>> mq;
vector<vector<pair<pair<int, int>, int>>> oq(pret);
repIn2(ab, qi, queries) {
auto [a, b] = ab;
if(over[a] != over[b]) mq.pb({{min(inEu[a], inEu[b]), max(inEu[a], inEu[b])}, qi});
else oq[inEu[over[a]]].pb({ab, qi});
}
queries.clear();
int lt = 0;
repIn2(k, vl, edges) vl = lt++;
tB = 1 << (32 - __builtin_clz(max(2, lt) - 1));
squirt = (int)sqrt(pret);
ranges::sort(mq, mosCmp);
int l = 0, r = 0;
rep(i, 1, 2 * tB) ts[i] = t1[i] = 0;
repIn2(ab, qi, mq) {
auto [a, b] = ab;
while(l > a) {
int cv = eu[l];
int u = eu[--l];
if(dep[u] == dep[cv]) continue;
tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
}
while(r < b) {
int cv = eu[r];
int u = eu[++r];
if(dep[u] == dep[cv]) continue;
tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
}
while(l < a) {
int cv = eu[l];
int u = eu[++l];
if(dep[u] == dep[cv]) continue;
tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
}
while(r > b) {
int cv = eu[r];
int u = eu[--r];
if(dep[u] == dep[cv]) continue;
tAdd(edges[abs(dep[u] - dep[cv])], dep[u] - dep[cv], 1);
}
auto usable = tQ(qAvail[qi]);
auto all = t1[1];
DEBUG {
DC << "For query " << qi << "\n interval eu (" << l << ' ' << r << "): ";
rep(i, l, r + 1) DC << eu[i] << ' ';
DC << "\n usable " << usable << "\n all " << all << eol;
}
if(usable + qAvail2[qi] < all) answers[qi] = -1;
else answers[qi] = qAvail2[qi] - (all - usable);
}
mq.clear();
off[v] = true;
repIn2(u, c, g[v]) if(!off[u]) decompose(u, oq[inEu[u]]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q;
int a, b, c, d;
ogE.resize(n - 1);
rep(i, 0, n - 1) cin >> ogE[i].first >> ogE[i].second;
costs.resize(n - 1);
rep(i, 0, m) {
cin >> a >> b;
costs[--a].pb(b);
}
int newNodes = 0;
rep(i, 0, n - 1) newNodes += max(0, (int)costs[i].size() - 1);
g.resize(n + 1 + newNodes);
newNodes = 0;
rep(i, 0, n - 1) {
auto [x, y] = ogE[i];
if(costs[i].empty()) {g[x].pb({y, 0}), g[y].pb({x, 0}); continue;}
int last = x;
rep(j, 0, (int)costs[i].size() - 1) g[last].pb({n + 1 + newNodes, costs[i][j]}), g[n + 1 + newNodes].pb({last, costs[i][j]}), last = n + 1 + newNodes++;
g[last].pb({y, costs[i].back()}), g[y].pb({last, costs[i].back()});
}
DEBUG {
DC << "Graph :\n";
rep(i, 1, (int)g.size()) repIn2(j, cc, g[i]) DC << i << ' ' << j << ' ' << cc << eol;
DC << eol;
}
n = (int)g.size();
subS.resize(n);
inEu.resize(n);
eu.resize(2 * n + 5);
over.resize(n);
answers.resize(q);
dep.resize(n);
qAvail.resize(q);
qAvail2.resize(q);
off.resize(n);
int maxTB = 1 << (32 - __builtin_clz(n + 1));
ts.resize(2 * maxTB);
t1.resize(2 * maxTB);
vector<pair<pair<int, int>, int>> queries(q);
rep(i, 0, q) {
cin >> a >> b >> c >> d;
queries[i] = {{a, b}, i};
qAvail[i] = d;
qAvail2[i] = c;
}
decompose(1, queries);
rep(i, 0, q) cout << answers[i] << '\n';
}
# | 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... |