/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, q;
vector<int> G[maxn];
struct ask
{
int s, t, x, y;
} que[maxn];
int p[maxn];
int c[maxn];
struct cp
{
int p, c;
bool operator<(const cp &x)
{
return c < x.c;
}
} ch[maxn];
struct BIT
{
ll bit[maxn];
void init()
{
memset(bit, 0, sizeof(bit));
}
void upd(int id, ll val)
{
for (id; id <= n; id += id & -id)
{
bit[id] += val;
}
}
ll get(int id)
{
ll res = 0;
for (id; id >= 1; id -= id & -id)
{
res += bit[id];
}
return res;
}
} A, B;
int tin[maxn];
int tout[maxn];
int s = 0;
int par[maxn];
pair<int, int> rmq[maxn][20];
int eu1[maxn];
int tin1[maxn];
int tout1[maxn];
int s1 = 0;
void dfs(int u, int pa)
{
tin[u] = ++s;
tin1[u] = ++s1;
eu1[s1] = u;
for (auto v : G[u])
{
if (v == pa)
continue;
par[v] = u;
dfs(v, u);
eu1[++s1] = u;
}
tout[u] = s;
}
void init()
{
for (int i = 1; i <= s1; i++)
{
rmq[i][0] = {tin1[eu1[i]], eu1[i]};
}
for (int i = 1; (1 << i) <= s1; i++)
{
for (int j = 1; j + (1 << i) - 1 <= s1; j++)
{
rmq[j][i] = min(rmq[j + (1 << (i - 1))][i - 1], rmq[j][i - 1]);
}
}
}
int LCA(int u, int v)
{
if (tin1[u] > tin1[v])
swap(u, v);
int dis = 31 - __builtin_clz(tin1[v] - tin1[u] + 1);
return min(rmq[tin1[u]][dis], rmq[tin1[v] - (1 << dis) + 1][dis]).se;
}
int l[maxn];
int ans[maxn];
int r[maxn];
pair<int, int> ed[maxn];
vector<int> K[maxn];
void solve()
{
cin >> n >> m >> q;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
ed[i].fi = a;
ed[i].se = b;
G[a].pb(b);
G[b].pb(a);
}
dfs(1, -1);
init();
for (int i = 1; i <= m; i++)
{
cin >> ch[i].p >> ch[i].c;
if (par[ed[ch[i].p].fi] == ed[ch[i].p].se)
{
ch[i].p = ed[ch[i].p].fi;
}
else
{
ch[i].p = ed[ch[i].p].se;
}
}
sort(ch + 1, ch + 1 + m);
for (int i = 1; i <= q; i++)
{
cin >> que[i].s >> que[i].t >> que[i].x >> que[i].y;
ans[i] = 1e9;
l[i] = 0;
r[i] = m;
}
for (int _ = 1; _ <= 18; _++)
{
for (int i = 1; i <= q; i++)
{
if (l[i] <= r[i])
{
int mid = (l[i] + r[i]) >> 1;
K[mid].pb(i);
}
}
A.init();
B.init();
for (int i = 1; i <= m; i++)
{
A.upd(tin[ch[i].p], 1);
A.upd(tout[ch[i].p] + 1, -1);
}
for (int i = 0; i <= m; i++)
{
if (i)
{
B.upd(tin[ch[i].p], ch[i].c);
B.upd(tout[ch[i].p] + 1, -ch[i].c);
// cout << tin[ch[i].p] << " " << tout[ch[i].p] << " " << ch[i].c << "\n";
A.upd(tin[ch[i].p], -1);
A.upd(tout[ch[i].p] + 1, 1);
}
for (auto v : K[i])
{
int u = LCA(que[v].s, que[v].t);
int silver = B.get(tin[que[v].s]) + B.get(tin[que[v].t]) - 2 * B.get(tin[u]);
// cout << que[v].s << " " << que[v].t << " " << u << "\n";
int gold = A.get(tin[que[v].s]) + A.get(tin[que[v].t]) - 2 * A.get(tin[u]);
if (silver <= que[v].y)
{
ans[v] = gold;
l[v] = i + 1;
}
else
{
r[v] = i - 1;
}
}
K[i].clear();
}
}
for (int i = 1; i <= q; i++)
{
if (ans[i] <= que[i].x)
{
cout << que[i].x - ans[i] << "\n";
}
else
{
cout << "-1\n";
}
}
}
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
solve();
}
Compilation message
currencies.cpp: In member function 'void BIT::upd(int, ll)':
currencies.cpp:58:14: warning: statement has no effect [-Wunused-value]
58 | for (id; id <= n; id += id & -id)
| ^~
currencies.cpp: In member function 'll BIT::get(int)':
currencies.cpp:66:14: warning: statement has no effect [-Wunused-value]
66 | for (id; id >= 1; id -= id & -id)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6564 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6568 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
7476 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6568 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6564 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6568 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
7476 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
