#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;
#define maxn 200005
#define lg 18
ll n,m,q;
vector<ll> g[maxn];
ll in[maxn],out[maxn],st[lg][maxn],ti = 0;
ll in2[maxn],out2[maxn],ti2 = 0;
pll e[maxn];
vector<pll> v;
void dfs1(ll u,ll p){
in[u] = ++ti;
in2[u] = ++ti2;
st[0][u] = p;
for(ll s : g[u]){
if(s==p) continue;
dfs1(s,u);
}
out[u] = ++ti;
out2[u] = ti2 - 1;
}
bool intree(ll x,ll y){return in2[y]<=in2[x]&&out2[y]>=out2[x];}
ll lca(ll x,ll y){
if(intree(x,y)) return y;
if(intree(y,x)) return x;
for(ll j = lg-1;j>=0;j--){
if(!intree(x,st[j][y])) y = st[j][y];
}
return st[0][y];
}
struct segtree{
ll t[2*maxn],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
segtree(){};
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
if(tl==tr) return;
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll i,ll x){
if(tl==tr){t[v]+=x;return;}
ll mid = (tl+tr)/2;
if(i<=mid) upd(ls[v],tl,mid,i,x);
else upd(rs[v],mid+1,tr,i,x);
t[v] = t[ls[v]] + t[rs[v]];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
if(l>r||l>tr||tl>tr||tl>r) return 0;
if(tl>=l&&tr<=r) return t[v];
ll mid = (tl+tr)/2;
return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
}
} tsum,tcnt,tg;
vector<ll> Q[maxn];
ll L[maxn],R[maxn],MID[maxn];
ll sta[maxn],en[maxn],au[maxn],ag[maxn];
ll ansl[maxn];
ll ansr[maxn];
ll rez[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m >> q;
for(ll i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
e[i] = {x,y};
g[x].pb(y);
g[y].pb(x);
}
v.pb({-1,-1});
for(ll i = 1;i<=m;i++){
ll j,w; cin >> j >> w;
v.pb({w,j});
}
sort(all(v));
dfs1(1,1);
tsum.init(tsum.root,1,ti);
tcnt.init(tcnt.root,1,ti);
tg.init(tg.root,1,ti);
for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]];
for(ll i = 1;i<=q;i++) cin >> sta[i] >> en[i] >> au[i] >> ag[i];
for(ll i = 1;i<=q;i++){
L[i] = 0,R[i] = m;
ansl[i] = -1;
ansr[i] = m+1;
rez[i] = 0;
}
bool change = 1;
while(change){
for(ll i = 0;i<=m;i++) Q[i].clear();
change = 0;
for(ll i = 1;i<=q;i++){
if(L[i]>R[i]) continue;
change = 1;
MID[i] = (L[i] + R[i])/2;
Q[MID[i]].pb(i);
}
//here;
for(ll i = m;i>=0;i--){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tg.upd(1,1,ti,in[x],1);
tg.upd(1,1,ti,out[x],-1);
}
}
//here;
for(ll i = 0;i<=m;i++){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
//cerr<<"w: "<<x<< " "<<y<< " "<<w<<endl;
tsum.upd(1,1,ti,in[x],w);
tsum.upd(1,1,ti,out[x],-w);
tcnt.upd(1,1,ti,in[x],1);
tcnt.upd(1,1,ti,out[x],-1);
tg.upd(1,1,ti,in[x],-1);
tg.upd(1,1,ti,out[x],1);
}
for(ll j : Q[i]){
ll x = sta[j],y = en[j],c = au[j],d = ag[j];
ll z = lca(x,y);
//cerr<<"LCA: "<<x<< " "<<y<<" "<<z<<endl;
ll cur = 0;
ll cntg = 0;
if(z!=x&&z!=y){
cur = tsum.sum(1,1,ti,in[z]+1,in[x]) + tsum.sum(1,1,ti,in[z]+1,in[y]);
cntg = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]);
}else{
if(x==z) swap(x,y);
cur = tsum.sum(1,1,ti,in[z]+1,in[x]);
cntg = tg.sum(1,1,ti,in[z]+1,in[x]);
}
if(cur<=d){
ansr[j] = MID[j];
rez[j] = cntg;
L[j] = MID[j] + 1;
}else R[j] = MID[j] - 1;
//if(j==8) cerr<<"j: "<<x<< " "<<y<< " "<<d<< " "<<cur<<endl;
}
Q[i].clear();
}
for(ll i = 0;i<=m;i++){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tsum.upd(1,1,ti,in[x],-w);
tsum.upd(1,1,ti,out[x],w);
tcnt.upd(1,1,ti,in[x],-1);
tcnt.upd(1,1,ti,out[x],1);
}
}
}
for(ll i = 1;i<=q;i++){
L[i] = 0,R[i] = m;
}
change = 1;
while(change){
for(ll i = 0;i<=m;i++) Q[i].clear();
change = 0;
for(ll i = 1;i<=q;i++){
if(L[i]>R[i]) continue;
change = 1;
MID[i] = (L[i] + R[i])/2;
Q[MID[i]].pb(i);
}
//here;
for(ll i = m;i>=0;i--){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tg.upd(1,1,ti,in[x],1);
tg.upd(1,1,ti,out[x],-1);
}
for(ll j : Q[i]){
ll x = sta[j],y = en[j],c = au[j],d = ag[j];
ll z = lca(x,y);
ll cur = 0;
if(z!=x&&z!=y){
cur = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]);
}else{
if(x==z) swap(x,y);
cur = tg.sum(1,1,ti,in[z]+1,in[x]);
}
if(cur<=c){
ansl[j] = MID[j];
R[j] = MID[j] - 1;
}else L[j] = MID[j] + 1;
}
Q[i].clear();
}
for(ll i = m;i>=0;i--){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tg.upd(1,1,ti,in[x],-1);
tg.upd(1,1,ti,out[x],1);
}
}
}
for(ll i = 1;i<=q;i++){
if(ansl[i]>ansr[i]){
cout<<-1<<endl;
continue;
}else cout<<au[i] - rez[i]<<endl;
}
return 0;
}
/**
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63
**/
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:120:20: warning: unused variable 'w' [-Wunused-variable]
120 | ll w = v[i].fi;
| ^
currencies.cpp:140:41: warning: unused variable 'c' [-Wunused-variable]
140 | ll x = sta[j],y = en[j],c = au[j],d = ag[j];
| ^
currencies.cpp:192:20: warning: unused variable 'w' [-Wunused-variable]
192 | ll w = v[i].fi;
| ^
currencies.cpp:197:51: warning: unused variable 'd' [-Wunused-variable]
197 | ll x = sta[j],y = en[j],c = au[j],d = ag[j];
| ^
currencies.cpp:217:20: warning: unused variable 'w' [-Wunused-variable]
217 | ll w = v[i].fi;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9940 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9996 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9920 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9940 KB |
Output is correct |
| 5 |
Correct |
63 ms |
11340 KB |
Output is correct |
| 6 |
Correct |
75 ms |
11596 KB |
Output is correct |
| 7 |
Incorrect |
63 ms |
11236 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9940 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
11632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9940 KB |
Output is correct |
| 2 |
Incorrect |
69 ms |
11684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9940 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9996 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9920 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9940 KB |
Output is correct |
| 5 |
Correct |
63 ms |
11340 KB |
Output is correct |
| 6 |
Correct |
75 ms |
11596 KB |
Output is correct |
| 7 |
Incorrect |
63 ms |
11236 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
