#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+1,e);
}
}
void update(int S, int N){
if(s==e){
val+=(long long)s*N;
cnt+=N;
return;
}
prop();
if(S<=m) l->update(S,N);
else r->update(S,N);
val=l->val+r->val;
cnt=l->cnt+r->cnt;
}
int query(long long V){
if(s==e){
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[200005],eul;
int fi[200005],se[200005];
long long cost[200005];
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 = 200050;
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] = 1;
for (int k = 0; k < LOGN; ++k) {
if (p[k][x] == -1) break;
p[k+1][x] = p[k][p[k][x]];
}
for (int it:adj[x]) {
if (visited[it]) continue;
p[0][it] = x;
h[it] = h[x] + 1;
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&1)==0) 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+1;
for(int i=0; i<m; i++){
int a;
long long b;
cin >> a >> b;
cost[cnt]=b;
edges.push_back({cnt,edges[a-1].second});
edges[a-1].second=cnt;
cnt++;
}
for(auto i:edges){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
dfs(1,-1);
dfss(1);
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=0; i<q; i++){
int a,b;
long long c,d;
cin >> a >> b >> c >> d;
org[i]={a,b};
int x=0,y=0,o=-1;
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=0,c2=0,nds=0;
root=new node(0,1000000005);
int got[cnt];
memset(got,0,sizeof(got));
for(int i=0; i<q; i++){
while(c2<=qu[i].first.second){
if(got[eul[c2]]==0){
got[eul[c2]]=1;
nds++;
root->update(cost[eul[c2]],1);
}
else{
got[eul[c2]]=0;
nds--;
root->update(cost[eul[c2]],-1);
}
c2++;
}
while(c1>qu[i].second.second){
c1--;
if(got[eul[c1]]==0){
got[eul[c1]]=1;
nds++;
root->update(cost[eul[c1]],1);
}
else{
got[eul[c1]]=0;
nds--;
root->update(cost[eul[c1]],-1);
}
}
while(c2>qu[i].first.second+1){
c2--;
if(got[eul[c2]]==0){
got[eul[c2]]=1;
nds++;
root->update(cost[eul[c2]],1);
}
else{
got[eul[c2]]=0;
nds--;
root->update(cost[eul[c2]],-1);
}
}
while(c1<qu[i].second.second){
if(got[eul[c1]]==0){
got[eul[c1]]=1;
nds++;
root->update(cost[eul[c1]],1);
}
else{
got[eul[c1]]=0;
nds--;
root->update(cost[eul[c1]],-1);
}
c1++;
}
if(qu[i].second.first.first!=-1){
int o=qu[i].second.first.first;
if(got[o]==0){
got[o]=1;
nds++;
root->update(cost[o],1);
}
else{
assert(false);
}
}
int heh=root->query(qu[i].second.first.second.second);
ans[qu[i].second.first.second.first]-=(h[eul[c1]]+h[eul[c2-1]]-2*h[lca(eul[c1],eul[c2-1])]+1-heh);
if(qu[i].second.first.first!=-1){
int o=qu[i].second.first.first;
if(got[o]==0){
got[o]=1;
nds++;
root->update(cost[o],1);
}
else{
got[o]=0;
nds--;
root->update(cost[o],-1);
}
}
}
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 |
16 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
16 ms |
37864 KB |
Output is correct |
| 3 |
Correct |
16 ms |
37912 KB |
Output is correct |
| 4 |
Correct |
14 ms |
37892 KB |
Output is correct |
| 5 |
Incorrect |
69 ms |
42808 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
74 ms |
38616 KB |
Output is correct |
| 3 |
Correct |
75 ms |
38600 KB |
Output is correct |
| 4 |
Correct |
76 ms |
38588 KB |
Output is correct |
| 5 |
Execution timed out |
5104 ms |
64320 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
85 ms |
43400 KB |
Output is correct |
| 3 |
Correct |
81 ms |
43392 KB |
Output is correct |
| 4 |
Correct |
81 ms |
43348 KB |
Output is correct |
| 5 |
Execution timed out |
5081 ms |
179328 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
16 ms |
37864 KB |
Output is correct |
| 3 |
Correct |
16 ms |
37912 KB |
Output is correct |
| 4 |
Correct |
14 ms |
37892 KB |
Output is correct |
| 5 |
Incorrect |
69 ms |
42808 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
