| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1126496 | Pekiban | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const int N = 1e5+5 , LOG = 18;
struct EUDQ {
vector<int> g[N];
int D[N], up[LOG][N], tin[N], tout[N], n, tm = 0;
ll lz[4*N];
void dfs(int s, int e = -1) {
tin[s] = ++tm;
for (auto u : g[s]) {
if (u == e) continue;
D[u] = D[s] + 1, up[0][u] = s;
dfs(u, s);
}
tout[s] = tm;
}
int jump(int u, int k) {
for (int i = LOG-1; i >= 0; --i) {
if ((k >> i) & 1) u = up[i][u];
}
return u;
}
void init() {
dfs(1);
for (int i = 1; i < LOG; ++i) {
for (int j = 1; j < N; ++j) {
up[i][j] = up[i-1][up[i-1][j]];
}
}
}
void reset() {
fill(lz, lz+4*(n+1), 0);
}
int lca(int u, int v) {
if (D[u] < D[v]) swap(u, v);
u = jump(u, D[u] - D[v]);
if (u == v) return u;
for (int i = LOG-1; i >= 0; --i) {
if (up[i][u] != up[i][v]) u = up[i][u], v = up[i][v];
}
return up[0][u];
}
void push(int i) {
if (lz[i]) {
lz[2*i] += lz[i];
lz[2*i+1] += lz[i];
lz[i] = 0;
}
}
void upd(int l, int r, int x, int i, int l2, int r2) {
if (l <= l2 && r2 <= r) {
lz[i] += x;
return;
}
push(i);
int m2 = (l2 + r2)/2;
if (l <= m2) upd(l, r, x, 2*i, l2, m2);
if (m2+1 <= r) upd(l, r, x, 2*i+1, m2+1, r2);
}
void add(int u, int v, int x) {
if (D[u] < D[v]) swap(u, v);
upd(tin[u], tout[u], x, 1, 1, n);
}
ll qry(int p, int i, int l2, int r2) {
if (l2 == r2) return lz[i];
push(i);
int m2 = (l2 + r2)/2;
if (p <= m2) return qry(p, 2*i, l2, m2);
return qry(p, 2*i+1, m2+1, r2);
}
ll qry(int p) {
return qry(p, 1, 1, n);
}
ll calc(int u, int v) {
return qry(tin[u]) + qry(tin[v]) - 2*qry(tin[lca(u, v)]);
}
} T;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q; T.n = n;
array<int, 2> E[n];
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
T.g[u].pb(v); T.g[v].pb(u);
E[i] = {u, v};
}
pair<int, int> e[m+1];
for (int i = 1; i <= m; ++i) {
cin >> e[i].first >> e[i].second;
}
sort(e+1, e+m+1);
for (int i = 1; i <= m; ++i) swap(e[i][0], e[i][1]);
array<ll, 4> qu[q+1];
for (int i = 1; i <= q; ++i) {
cin >> qu[i][0] >> qu[i][1] >> qu[i][2] >> qu[i][3];
}
for (int i = 1; i <= q; ++i) {
cout << qu[i][0] << ' ' << qu[i][1] << ' ' << qu[i][2] << ' ' << qu[i][3] << '\n';
}
for (int i = 1; i <= m; ++i) {
T.add(E[e[i][0]][0], E[e[i][0]][1], e[i][1]);
for (int j = 1; j <= q; ++j) {
if (T.calc(qu[j][0], qu[j][1]) <= qu[j][3]) P[j] = i;
}
}
T.reset();
vector<int> B[m+1];
for (int i = 1; i <= q; ++i) B[P[i]].pb(i);
for (int i = 0; i <= m; ++i) {
if (i) T.add(E[e[i][0]][0], E[e[i][0]][1], 1);
for (auto j : B[i]) {
qu[j][2] += T.calc(qu[j][0], qu[j][1]);
}
}
for (int i = 1; i <= q; ++i) {
cout << max(-1LL, qu[i][2] - T.calc(qu[i][0], qu[i][1])) << '\n';
}
}