#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int dp[100005][20];
int lv[100005];
vector<int>v[100005];
vector<pair<int,int> >edge;
vector<int>cp[100005];
map<pair<int,int>,int>mp;
vector<int>vl;
struct pstree{
struct node{
node *l,*r;
int val;
int cnt;
node(int x=0){
val=x;
cnt=0;
l=r=NULL;
}
};
typedef node* pnode;
pnode root[100005];
int getval(pnode x){
return x?x->val:0;
}
int getcnt(pnode x){
return x?x->cnt: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 init(){
build(1,n,root[0]);
}
void upd(int st,int en,pnode &x,int pos,int val,pnode k){
x=new node(*k);
if(st==en){
x->val+=val;
x->cnt++;
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->val=getval(x->l)+getval(x->r);
x->cnt=getcnt(x->l)+getcnt(x->r);
}
int fkval(int st,int en,pnode x,pnode y,pnode l,int val,int cnt){
if(st==en){
int ad=val/vl[st-1];
return cnt+ad;
}
//cerr<<st<<" "<<en<<" "<<x->val<<" "<<y->val<<" "<<l->val<<endl;
int sum=getval(x->l)+getval(y->l)-2*getval(l->l);
//cerr<<"sum,val "<<sum<<" "<<val<<endl;
int m=(st+en)/2;
if(sum>=val){
return fkval(st,m,x->l,y->l,l->l,val,cnt);
}else{
//cerr<<m+1<<" "<<en<<" "<<x->r<<" "<<y->r<<" "<<val-sum<<" "<<cnt+getcnt(x->l)+getcnt(y->l)-2*getcnt(l->l)<<endl;
return fkval(m+1,en,x->r,y->r,l->r,val-sum,cnt+getcnt(x->l)+getcnt(y->l)-2*getcnt(l->l));
}
}
}pst;
void dfs(int x,int p){
lv[x]=lv[p]+1;
dp[x][0]=p;
pair<int,int>pp={x,p};
int np=mp[{x,p}];
pst.root[x]=pst.root[p];
for(int i=0;i<cp[np].size();i++){
int pos=lower_bound(vl.begin(),vl.end(),cp[np][i])-vl.begin()+1;
pst.upd(1,n,pst.root[x],pos,cp[np][i],pst.root[x]);
}
//cout<<x<<" "<<pst.root[x]<<endl;
for(int i=1;i<20;i++){
dp[x][i]=dp[dp[x][i-1]][i-1];
}
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=p)dfs(v[x][i],x);
}
}
int lca(int a,int b){
//cerr<<"finding lca "<<a<<" "<<b<<endl;
if(lv[b]>lv[a])swap(a,b);
//cerr<<lv[a]<<" "<<lv[b]<<endl;
for(int i=19;i>=0;i--)if(lv[dp[a][i]]>=lv[b])a=dp[a][i];
//cerr<<"change lv:"<<" "<<a<<" "<<b<<endl;
if(a==b)return a;
for(int i=19;i>=0;i--)if(dp[a][i]!=dp[b][i])a=dp[a][i],b=dp[b][i];
//cerr<<"bf lca"<<a<<" "<<b<<endl;
return dp[a][0];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>q;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
edge.push_back({a,b});
v[b].push_back(a);
v[a].push_back(b);
mp[{a,b}]=i;
mp[{b,a}]=i;
}
for(int i=0;i<m;i++){
int p,c;
cin>>p>>c;
p--;
cp[p].push_back(c);
vl.push_back(c);
}
sort(vl.begin(),vl.end());
pst.init();
dfs(1,0);
for(int i=0;i<q;i++){
//cerr<<"question "<<i<<endl;
int s,t,x,y;
cin>>s>>t>>x>>y;
int l=lca(s,t);
//cerr<<"lca:"<<l<<endl;
//cerr<<pst.root[s]<<" "<<pst.root[t]<<" "<<pst.root[l]<<endl;
int sil=pst.fkval(1,n,pst.root[s],pst.root[t],pst.root[l],y,0);
int all=pst.getcnt(pst.root[s])+pst.getcnt(pst.root[t])-pst.getcnt(pst.root[l])*2;
int left=all-sil;
int gl=x-left;
if(gl>=0){
cout<<gl<<"\n";
}else{
cout<<"-1\n";
}
//cerr<<endl;
}
}
Compilation message
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<cp[np].size();i++){
| ~^~~~~~~~~~~~~~
currencies.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
currencies.cpp:76:18: warning: variable 'pp' set but not used [-Wunused-but-set-variable]
76 | pair<int,int>pp={x,p};
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
12984 KB |
Execution killed with signal 8 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
13148 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
12984 KB |
Execution killed with signal 8 |
| 3 |
Halted |
0 ms |
0 KB |
- |
