| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1257459 | nguyn | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int N = 1e5 + 5;
struct BIT {
int n;
vector<ll> bit;
BIT() {}
BIT(int _n) : n(_n) {
bit.assign(n + 3, 0);
}
void update(int id, ll val) {
for (int i = id; i <= n; i += (i & -i)) bit[i] += val;
}
ll get(int id) {
ll ret = 0;
for (int i = id; i > 0; i -= (i & -i)) ret += bit[i];
return ret;
}
ll get(int u, int v) {
return get(v) - get(u - 1);
}
} sum, cnt;
struct Query {
int u, v, x; ll y;
} que[N];
int n, m, q;
vector<int> g[N];
int tin[N], tout[N];
pii edges[N];
int res[N];
int l[N], r[N];
int timedfs = 0;
vector<int> ev[N];
vector<pair<ll, int>> vec;
int anc[N], up[N][17], h[N];
void pre_dfs(int u, int p) {
tin[u] = ++timedfs;
for (int v : g[u]) {
if (v == p) continue;
up[v][0] = u;
h[v] = h[u] + 1;
for (int i = 1; i < 17; i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
pre_dfs(v, u);
}
tout[u] = ++timedfs;
}
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int i = 0; (1 << i) <= k; i++) {
if (k >> i & 1) u = up[u][i];
}
}
if (u == v) return u;
for (int i = 16; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
edges[i] = {u, v};
}
pre_dfs(1, 0);
for (int i = 1; i <= m; i++) {
int p, c;
int u, v;
cin >> p >> c;
tie(u, v) = edges[p];
if (v == up[u][0]) swap(u, v);
vec.pb({c, v});
}
for (int i = 1; i <= q; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
que[i] = {u, v, x, y};
anc[i] = lca(u, v);
l[i] = 0;
r[i] = vec.size() - 1;
}
sort(vec.begin(), vec.end());
while(1) {
bool ok = 0;
for (int i = 1; i <= q; i++) {
if (l[i] <= r[i]) {
int mid = (l[i] + r[i]) / 2;
ok = 1;
ev[mid].pb(i);
}
}
if (!ok) break;
sum = BIT(2 * n);
cnt = BIT(2 * n);
for (int i = 0; i < vec.size(); i++) {
cnt.update(tin[vec[i].S], 1);
cnt.update(tout[vec[i].S], - 1);
sum.update(tin[vec[i].S], vec[i].F);
sum.update(tout[vec[i].S], - vec[i].F);
for (int id : ev[i]) {
ll tmp = sum.get(tin[anc[id]] + 1, tin[que[id].u]) + sum.get(tin[anc[id]] + 1, tin[que[id].v]);
if (tmp <= que[id].y) {
res[id] = cnt.get(tin[anc[id]] + 1, tin[que[id].u]) + cnt.get(tin[anc[id]] + 1, tin[que[id].v]);
l[id] = i + 1;
}
else {
r[id] = i - 1;
}
}
ev[i].clear();
}
}
cnt = BIT(2 * n);
for (int i = 0; i < vec.size(); i++) {
cnt.update(tin[vec[i].S], 1);
cnt.update(tout[vec[i].S], -1);
}
for (int i = 1; i <= q; i++) {
int c = cnt.get(tin[anc[i]] + 1, tin[que[i].u]) + cnt.get(tin[anc[i]] + 1, tin[que[i].v]);
// cout << c << ' ' << res[i] << ' ' << que[i].x << ' ';
c -= res[i];
cout << max(-1, que[i].x - c) << '\n';
}
}