#include <bits/stdc++.h>
using namespace std;
long long przod[100007][19];
long long gl[100007];
long long preord[100007];
long long prawk[100007];
long long ilemaxx[100007];
long long odp[100007];
long long n, m, q;
vector<long long> graph[100007];
vector<pair<long long, long long>> bramki;
long long t = 0;
long long drz[262150];
long long drz2[262150];
struct zapyt{
long long ind, l, r, lca, s, t, x, y;
};
bool sfunkc(const zapyt& a, const zapyt& b)
{
return ((a.l + a.r) / 2) < ((b.l + b.r) / 2);
}
void dfs(long long cur, long long pop)
{
gl[cur] = gl[pop] + 1;
preord[cur] = t;
prawk[cur] = t;
t++;
if(pop != -1)
{
przod[cur][0] = pop;
}
for(auto x : graph[cur])
{
if(x != pop)
{
dfs(x, cur);
prawk[cur] = max(prawk[cur], prawk[x]);
}
}
}
long long lca(long long a, long long b)
{
if(gl[a] > gl[b])
{
swap(a, b);
}
for(long long i = 18; i >= 0; i--)
{
if(gl[przod[b][i]] >= gl[a])
{
b = przod[b][i];
}
}
if(a == b)
{
return a;
}
for(long long i = 18; i >= 0; i--)
{
if(przod[a][i] != przod[b][i])
{
a = przod[a][i];
b = przod[b][i];
}
}
return przod[a][0];
}
void policzlca()
{
przod[1][0] = 1;
for(long long i = 1; i < 19; i++)
{
for(long long j = 1; j <= n; j++)
{
przod[j][i] = przod[przod[j][i - 1]][i - 1];
}
}
}
void dodaj(long long l, long long r, long long curl, long long curr, long long gdzie, long long ile)
{
if(l > curr || r < curl)
{
return;
}
else if(l <= curl && curr <= r)
{
drz[gdzie] += ile;
}
else
{
dodaj(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile);
dodaj(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile);
}
}
long long sumap(long long gdzie)
{
gdzie += 131072;
long long suma = 0;
while(gdzie != 0)
{
suma += drz[gdzie];
gdzie /= 2;
}
return suma;
}
void dodaj2(long long l, long long r, long long curl, long long curr, long long gdzie, long long ile)
{
if(l > curr || r < curl)
{
return;
}
else if(l <= curl && curr <= r)
{
drz2[gdzie] += ile;
}
else
{
dodaj2(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile);
dodaj2(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile);
}
}
long long sumap2(long long gdzie)
{
gdzie += 131072;
long long suma = 0;
while(gdzie != 0)
{
suma += drz2[gdzie];
gdzie /= 2;
}
return suma;
}
int main()
{
cin >> n >> m >> q;
vector<pair<long long, long long>> krawww;
for(long long i = 0; i < n - 1; i++)
{
long long a, b;
cin >> a >> b;
krawww.push_back({a, b});
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 0);
policzlca();
for(long long i = 0; i < m; i++)
{
long long p, c, gdzied;
cin >> p >> c;
if(gl[krawww[p - 1].first] > gl[krawww[p - 1].second])
{
gdzied = krawww[p - 1].first;
}
else
{
gdzied = krawww[p - 1].second;
}
bramki.push_back({c, gdzied});
}
sort(bramki.begin(), bramki.end());
vector<zapyt> wszystkiezapyt;
for(long long i = 0; i < q; i++)
{
long long s, t, x, y;
cin >> s >> t >> x >> y;
zapyt temp;
temp.l = 0;
temp.r = m;
temp.ind = i;
temp.lca = lca(s, t);
temp.x = x;
temp.y = y;
temp.s = s;
temp.t = t;
wszystkiezapyt.push_back(temp);
}
for(long long iter = 0; iter < 30; iter++)
{
sort(wszystkiezapyt.begin(), wszystkiezapyt.end(), sfunkc);
long long dulgp = 0;
for(long long i = 0; i < q; i++)
{
while(dulgp < (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2)
{
dodaj(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, bramki[dulgp].first);
dodaj2(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, 1);
dulgp++;
}
if(sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]) > wszystkiezapyt[i].y)
{
wszystkiezapyt[i].r = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2;
}
else
{
ilemaxx[wszystkiezapyt[i].ind] = sumap2(preord[wszystkiezapyt[i].s]) + sumap2(preord[wszystkiezapyt[i].t]) - 2 * sumap2(preord[wszystkiezapyt[i].lca]);
wszystkiezapyt[i].l = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2 + 1;
}
}
for(long long i = 0; i < 262147; i++)
{
drz[i] = 0;
drz2[i] = 0;
}
}
for(long long i = 0; i < m; i++)
{
dodaj(preord[bramki[i].second], prawk[bramki[i].second], 0, 131071, 1, 1);
}
for(long long i = 0; i < q; i++)
{
long long ilebram = sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]);
if(ilebram - ilemaxx[wszystkiezapyt[i].ind] - wszystkiezapyt[i].x <= 0)
{
odp[wszystkiezapyt[i].ind] = wszystkiezapyt[i].x - ilebram + ilemaxx[wszystkiezapyt[i].ind];
}
else
{
odp[wszystkiezapyt[i].ind] = -1;
}
}
for(long long i = 0; i < q; i++)
{
cout << odp[i] << endl;
}
}
# | 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... |