#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ppii = pair<int, pii>;
const int N = 1e5 + 5, L = 21;
int lowbit(int x){
return x & -x;
}
ll A[N], B[N], B2[N], n;
void upd(ll x, ll v, ll sus) {
for(ll i = x ; i <= n ; i += lowbit(i)){
B[i] += v;
B2[i] += sus;
}
}
pll query(ll x) {
pll ans = {0, 0};
for(ll i = x ; i > 0 ; i -= lowbit(i)){
ans.fi += B[i];
ans.se += B2[i];
}
return ans;
}
void update(ll l, ll r, ll v) {
upd(r + 1, -v, -1); upd(l, v, 1);
}
void init() {
fill(B, B + n + 1, 0);
fill(B2, B2 + n + 1, 0);
}
pii edge[N];
vector<int> e[N];
int tin[N], tout[N], timer = 0;
void dfs(int u, int par){
tin[u] = ++timer;
for(int v : e[u]){
if(v == par) continue;
dfs(v, u);
}
tout[u] = timer;
}
int par[N][L], dep[N];
void dfs2(int u, int p){
dep[u] = dep[p] + 1;
par[u][0] = p;
for(int i = 1; i < L; i++){
par[u][i] = par[par[u][i - 1]][i - 1];
}
for(int v : e[u]){
if(v == p) continue;
dfs2(v, u);
}
}
int gold[N];
void dfsgold(int u, int par){
for(int v : e[u]){
if(v == par) continue;
gold[v] += gold[u];
dfsgold(v, u);
}
}
int ancestork(int u, int dist){
for(int i = 0; i < L; i++){
if(dist >> i & 1) u = par[u][i];
}
return u;
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
u = ancestork(u, dep[u] - dep[v]);
if(u == v) return u;
for(int i = L - 1; i >= 0; i--){
if(par[v][i] != par[u][i]){
v = par[v][i];
u = par[u][i];
}
}
int l = par[v][0];
return l;
}
pll distroot(ll x){
return query(tin[x]);
}
pll path(int u, int v){
pll res = {0, 0};
pll p1 = distroot(u), p2 = distroot(v), p3 = distroot(lca(u, v));
res.fi = p1.fi + p2.fi - p3.fi;
res.se = p1.se + p2.se - p3.se;
return res;
}
int goldpath(int u, int v){
return gold[u] + gold[v] - gold[lca(u, v)];
}
pll p[N];
int s[N], t[N]; ll x[N], y[N];
struct bs{
int l, r, mid, id;
};
bs b[N];
int sus[N];
vector<bs> midcur[N];
void solve(){
int m, q;
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
edge[i] = {u, v};
}
for(int i = 1; i <= m; i++){
cin >> p[i].se >> p[i].fi;
}
sort(p + 1, p + m + 1);
dfs(1, -1);
dfs2(1, -1);
for(int i = 1; i < n; i++){
int u = edge[i].fi, v = edge[i].se;
if(tin[u] > tin[v]) swap(edge[i].fi, edge[i].se);
}
for(int i = 1; i <= m; i++){
gold[edge[p[i].se].se]++;
}
dfsgold(1, -1);
for(int i = 1; i <= q; i++){
cin >> s[i] >> t[i] >> x[i] >> y[i];
b[i] = {0, m, 1, i};
}
for(int z = 1; z < L; z++){
init();
for(int i = 1; i <= m; i++){
midcur[i].clear();
}
for(int i = 1; i <= q; i++){
b[i].mid = (b[i].l + b[i].r + 1) / 2;
midcur[b[i].mid].push_back(b[i]);
}
for(int i = 1; i <= m; i++){
int id = p[i].se;
int u = edge[id].fi, v = edge[id].se;
update(tin[v], tout[v], p[i].fi);
for(auto [l, r, mid, id] : midcur[i]){
if(l == r) continue;
u = s[id], v = t[id];
pll cur = path(u, v);
if(cur.fi <= y[id]){
b[id].l = mid;
sus[id] = cur.se;
}else{
b[id].r = mid - 1;
}
}
}
}
for(int i = 1; i <= q; i++){
int g = goldpath(s[i], t[i]);
int silver_used = sus[i];
int gold_used = g - silver_used;
if(gold_used > x[i]){
cout << -1 << endl;
}else{
cout << x[i] - gold_used << endl;
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
if(fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
int test = 1;
//cin >> test;
while(test--){
solve();
}
}
Compilation message (stderr)
currencies.cpp: In function 'int main()':
currencies.cpp:216:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | freopen(name".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |