#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int s,e,m;
long long val;
long long cnt;
node *l,*r;
node(int S, int E){
s=S; e=E; m=(s+e)/2LL;
l=r=NULL;
val=cnt=0LL;
}
void prop(){
if(l==NULL){
l=new node(s,m);
r=new node(m+1LL,e);
}
}
void update(int S, int N){
if(s==e){
if(N==1LL){
val+=(long long)s;
cnt++;
}
else{
val-=(long long)s;
cnt--;
}
return;
}
prop();
if(S<=m) l->update(S,N);
else r->update(S,N);
val=l->val+r->val;
cnt=l->cnt+r->cnt;
}
long long query(long long V){
if(s==e){
assert(s!=0LL);
return V/(long long)s;
}
prop();
if(l->val>V) return l->query(V);
else return l->cnt+r->query(V-l->val);
}
} *root;
vector<int> adj[300005],eul;
int fi[300005],se[300005];
long long cost[300005];
void dfs(int x, int p){
fi[x]=eul.size();
eul.push_back(x);
for(int i:adj[x]){
if(i!=p) dfs(i,x);
}
se[x]=eul.size();
eul.push_back(x);
}
const int MAXN = 300050;
const int LOGN = 20;
int p[LOGN+1][MAXN], h[MAXN]; //h: number of edges from root
bitset<MAXN> visited;
void dfss(int x) {
if (visited[x]) return;
visited[x] = 1LL;
for (int k = 0LL; k < LOGN; ++k) {
if (p[k][x] == -1LL) break;
p[k+1LL][x] = p[k][p[k][x]];
}
for (int it:adj[x]) {
if (visited[it]) continue;
p[0][it] = x;
h[it] = h[x] + 1LL;
dfss(it);
}
}
/* Query */
int lca(int a, int b) { //h[a] < h[b]
if (h[a] > h[b]) swap(a, b);
/* advance b by h[b] - h[a] parents */
for (int k = 0, d = h[b] - h[a]; k < LOGN; ++k) {
if (d & (1<<k)) b = p[k][b];
}
if (a == b) return a;
assert(h[a] == h[b]); //same height
/* to be continued */
for (int k = LOGN-1; k >= 0; --k) {
if (p[k][a] != p[k][b])
a = p[k][a], b = p[k][b];
}
assert(p[0][a] == p[0][b]); //same immediate parent
return p[0][a];
}
bool cmp(pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > a,pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > b){
if(a.first.first==b.first.first){
if((a.first.first&1LL)==0LL) return a.first.second<b.first.second;
else return a.first.second>b.first.second;
}
return a.first.first<b.first.first;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
memset(p,-1,sizeof(p));
int n,m,q;
cin >> n >> m >> q;
vector<pair<int,int> > edges;
for(int i=0; i<n-1; i++){
int a,b;
cin >> a >> b;
edges.push_back({a,b});
}
int cnt=n+1LL;
for(int i=0; i<m; i++){
int a;
long long b;
cin >> a >> b;
cost[cnt]=b;
edges.push_back({cnt,edges[a-1LL].second});
edges[a-1LL].second=cnt;
cnt++;
}
for(auto i:edges){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
dfs(1LL,-1LL);
dfss(1LL);
int buc=450LL;
long long ans[q];
pair<pair<int,int>,pair<pair<int,pair<int,long long> >,int> > qu[q];
pair<int,int> org[q];
for(int i=0LL; i<q; i++){
int a,b;
long long c,d;
cin >> a >> b >> c >> d;
org[i]={a,b};
int x=0LL,y=0LL,o=-1LL;
if(se[a]<fi[b]){
x=se[a]; y=fi[b];
o=lca(a,b);
}
else if(se[b]<fi[a]){
x=se[b]; y=fi[a];
o=lca(a,b);
}
else if(fi[a]<fi[b]){
x=fi[a]; y=fi[b];
}
else{
x=fi[b]; y=fi[a];
}
ans[i]=c;
qu[i]={{x/buc,y},{{o,{i,d}},x}};
}
sort(qu,qu+q,cmp);
int c1=0LL,c2=0LL,nds=0LL;
root=new node(0LL,2000000005LL);
int got[300005];
memset(got,0,sizeof(got));
for(int i=0LL; i<q; i++){
while(c2<=qu[i].first.second){
if(got[eul[c2]]==0LL){
got[eul[c2]]=1LL;
nds++;
root->update(cost[eul[c2]],1LL);
}
else{
got[eul[c2]]=0LL;
nds--;
root->update(cost[eul[c2]],-1LL);
}
c2++;
}
while(c1>qu[i].second.second){
c1--;
if(got[eul[c1]]==0LL){
got[eul[c1]]=1LL;
nds++;
root->update(cost[eul[c1]],1LL);
}
else{
got[eul[c1]]=0LL;
nds--;
root->update(cost[eul[c1]],-1LL);
}
}
while(c2>qu[i].first.second+1LL){
c2--;
if(got[eul[c2]]==0LL){
got[eul[c2]]=1LL;
nds++;
root->update(cost[eul[c2]],1LL);
}
else{
got[eul[c2]]=0LL;
nds--;
root->update(cost[eul[c2]],-1LL);
}
}
while(c1<qu[i].second.second){
if(got[eul[c1]]==0LL){
got[eul[c1]]=1LL;
nds++;
root->update(cost[eul[c1]],1LL);
}
else{
got[eul[c1]]=0LL;
nds--;
root->update(cost[eul[c1]],-1LL);
}
c1++;
}
if(qu[i].second.first.first!=-1LL){
int o=qu[i].second.first.first;
if(got[o]==0LL){
got[o]=1LL;
nds++;
root->update(cost[o],1LL);
}
else{
assert(false);
}
}
int heh=root->query(qu[i].second.first.second.second);
assert((eul[c1]==org[qu[i].second.first.second.first].first&&eul[c2-1]==org[qu[i].second.first.second.first].second)||(eul[c2-1]==org[qu[i].second.first.second.first].first&&eul[c1]==org[qu[i].second.first.second.first].second));
ans[qu[i].second.first.second.first]-=(h[eul[c1]]+h[eul[c2-1]]-2LL*h[lca(eul[c1],eul[c2-1])]+1LL-heh);
if(qu[i].second.first.first!=-1){
int o=qu[i].second.first.first;
if(got[o]==0LL){
got[o]=1LL;
nds++;
root->update(cost[o],1LL);
}
else{
got[o]=0LL;
nds--;
root->update(cost[o],-1LL);
}
}
}
for(int i=0; i<q; i++){
if(ans[i]<0LL) cout << -1 << '\n';
else cout << ans[i] << '\n';
}
}
/*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*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
59052 KB |
Output is correct |
| 2 |
Correct |
26 ms |
58956 KB |
Output is correct |
| 3 |
Correct |
27 ms |
58988 KB |
Output is correct |
| 4 |
Correct |
26 ms |
58956 KB |
Output is correct |
| 5 |
Incorrect |
87 ms |
64028 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
86 ms |
59816 KB |
Output is correct |
| 3 |
Correct |
91 ms |
59640 KB |
Output is correct |
| 4 |
Correct |
99 ms |
59720 KB |
Output is correct |
| 5 |
Execution timed out |
5093 ms |
83612 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
113 ms |
64468 KB |
Output is correct |
| 3 |
Correct |
118 ms |
64432 KB |
Output is correct |
| 4 |
Correct |
104 ms |
64436 KB |
Output is correct |
| 5 |
Execution timed out |
5105 ms |
200224 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
59052 KB |
Output is correct |
| 2 |
Correct |
26 ms |
58956 KB |
Output is correct |
| 3 |
Correct |
27 ms |
58988 KB |
Output is correct |
| 4 |
Correct |
26 ms |
58956 KB |
Output is correct |
| 5 |
Incorrect |
87 ms |
64028 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
