#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int pa[100005][20];
int lv[100005];
int ar[100005];
int info[100005];
vector<int>edcp[100005];
const int N=1e5;
pair<int,int>cp[100005];
vector<int>v[100005];
pair<int,int>edge[100005];
map<pair<int,int>,int >mp;
struct persist{
struct node{
long long sum,freq;
node *l;
node *r;
node(long long v=0,long long f=0){
sum=v;
freq=f;
l=NULL;
r=NULL;
}
};
typedef node* pnode;
pnode rt[100005]={};
int gsum(pnode x){
return x?x->sum:0;
}
int gfreq(pnode x){
return x?x->freq:0;
}
void build(int st,int en,pnode &x){
x=new node();
if(st==en){
return;
}
int m=(st+en)/2;
build(st,m,x->l);
build(m+1,en,x->r);
}
void build(){
build(1,N,rt[0]);
}
void upd(int st,int en,pnode &x,long long pos,long long val,pnode k){
if(k==NULL){
cout<<"NULL"<<endl;
}
x=new node(*k);
if(st==en){
x->sum+=val;
x->freq++;
return;
}
int m=(st+en)/2;
if(pos<=m){
upd(st,m,x->l,pos,val,k->l);
}else{
upd(m+1,en,x->r,pos,val,k->r);
}
x->sum=gsum(x->l)+gsum(x->r);
x->freq=gfreq(x->l)+gfreq(x->r);
}
void upd(int st,int en,long long pos,long long val,int check){
if(check==0){
rt[en]=new node(*rt[st]);
return;
}
if(rt[en]==NULL){
upd(1,N,rt[en],pos,val,rt[st]);
}else{
upd(1,N,rt[en],pos,val,rt[en]);
}
}
int fans(int st,int en,pnode p,pnode x,pnode y,long long k){
//cout<<st<<" "<<en<<" "<<k<<":"<<endl;
if(st==en){
long long f=x->freq+y->freq-2*p->freq;
//cout<<st<<" "<<ar[st]<<endl;
if(f==0){
return 0;
}
long long id=ar[st];
long long ans=min(k/id,f);
return ans;
}
//cout<<"sum: "<<gsum(x->l)<<" "<<gsum(p->l)<<" "<<gsum(y->l)<<" "<<gsum(p->l)<<" "<<endl;
long long sum=gsum(x->l)-gsum(p->l)+gsum(y->l)-gsum(p->l);
long long freq=gfreq(x->l)-gfreq(p->l)+gfreq(y->l)-gfreq(p->l);
//cout<<"sum,freq:"<<sum<<" "<<freq<<endl;
int m=(st+en)/2;
if(k<=sum){
//cout<<"go left"<<endl;
return fans(st,m,p->l,x->l,y->l,k);
}else{
//cout<<"go right"<<endl;
return fans(m+1,en,p->r,x->r,y->r,k-sum)+freq;
}
}
int fans(int p,int x,int y,long long k){
return fans(1,N,rt[p],rt[x],rt[y],k);
}
}pst;
void dfs(int i,int p){
//cout<<i<<" "<<p<<endl;
pa[i][0]=p;
lv[i]=lv[p]+1;
for(int j=1;j<20;j++){
pa[i][j]=pa[pa[i][j-1]][j-1];
}
int ednum=mp[{i,p}];
for(int j=0;j<edcp[ednum].size();j++){
int b=edcp[ednum][j];
int num=lower_bound(ar,ar+m+1,b)-ar;
//cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<endl;
pst.upd(p,i,num,b,1);
}
if(edcp[ednum].size()==0){
//cout<<"upd:NO UPD"<<endl;
pst.upd(p,i,0,0,0);
}
/*int id=mp[{i,p}];
int b=cp[id].second;
int num=lower_bound(ar,ar+m+1,b)-ar;
cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<id<<endl;
pst.upd(p,i,num,b);*/
for(int j=0;j<v[i].size();j++){
if(v[i][j]!=p){
dfs(v[i][j],i);
}
}
}
int lca(int a,int b){
if(lv[b]>lv[a]){
swap(a,b);
}
for(int i=19;i>=0;i--){
if(lv[pa[a][i]]>=lv[b]){
a=pa[a][i];
}
}
if(a==b){
return a;
}
for(int i=19;i>=0;i--){
if(pa[a][i]!=pa[b][i]){
a=pa[a][i];
b=pa[b][i];
}
}
return pa[a][0];
}
int main(){
cin>>n>>m>>q;
pst.build();
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
edge[i].first=a;
edge[i].second=b;
mp[{a,b}]=i;
mp[{b,a}]=i;
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
cp[i]={a,b};
int ednum=a;
edcp[a].push_back(b);
ar[i]=b;
}
/*for(int i=0;i<=n;i++){
cout<<ar[i]<<" ";
}*/
cout<<endl;
sort(ar+1,ar+m+1);
pst.upd(0,1,1,0,0);
dfs(1,0);
//cout<<"work"<<endl;
for(int i=1;i<=q;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
int x=lca(a,b);
int sz=pst.fans(x,a,b,LLONG_MAX);
//cout<<"SIZE IS "<<sz<<endl;
//cout<<"info"<<endl;
//cout<<x<<" "<<a<<" "<<b<<endl;
int use=pst.fans(x,a,b,d);
sz-=use;
c-=sz;
//cout<<"ANS::";
if(c<0){
cout<<"-1\n";
}else{
cout<<c<<"\n";
}
}
}
Compilation message
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j=0;j<edcp[ednum].size();j++){
| ~^~~~~~~~~~~~~~~~~~~
currencies.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j=0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:171:13: warning: unused variable 'ednum' [-Wunused-variable]
171 | int ednum=a;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14364 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14360 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
16492 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
16692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
16932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14364 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14360 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
16492 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
