#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);
assert(cnt*s==val);
return min(V/(long long)s,cnt);
}
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*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
58928 KB |
Output is correct |
2 |
Correct |
25 ms |
58988 KB |
Output is correct |
3 |
Correct |
25 ms |
58956 KB |
Output is correct |
4 |
Correct |
26 ms |
59060 KB |
Output is correct |
5 |
Correct |
86 ms |
63896 KB |
Output is correct |
6 |
Correct |
106 ms |
64024 KB |
Output is correct |
7 |
Correct |
96 ms |
62920 KB |
Output is correct |
8 |
Correct |
119 ms |
64392 KB |
Output is correct |
9 |
Correct |
110 ms |
64344 KB |
Output is correct |
10 |
Correct |
125 ms |
64432 KB |
Output is correct |
11 |
Correct |
135 ms |
64548 KB |
Output is correct |
12 |
Correct |
112 ms |
64328 KB |
Output is correct |
13 |
Correct |
104 ms |
64508 KB |
Output is correct |
14 |
Correct |
99 ms |
64460 KB |
Output is correct |
15 |
Correct |
103 ms |
64332 KB |
Output is correct |
16 |
Correct |
109 ms |
64432 KB |
Output is correct |
17 |
Correct |
105 ms |
64336 KB |
Output is correct |
18 |
Correct |
101 ms |
64324 KB |
Output is correct |
19 |
Correct |
130 ms |
64412 KB |
Output is correct |
20 |
Correct |
120 ms |
64312 KB |
Output is correct |
21 |
Correct |
114 ms |
64428 KB |
Output is correct |
22 |
Correct |
108 ms |
64428 KB |
Output is correct |
23 |
Correct |
39 ms |
64312 KB |
Output is correct |
24 |
Correct |
109 ms |
64384 KB |
Output is correct |
25 |
Correct |
94 ms |
64412 KB |
Output is correct |
26 |
Correct |
35 ms |
62452 KB |
Output is correct |
27 |
Correct |
36 ms |
63844 KB |
Output is correct |
28 |
Correct |
57 ms |
64416 KB |
Output is correct |
29 |
Correct |
66 ms |
64304 KB |
Output is correct |
30 |
Correct |
98 ms |
59768 KB |
Output is correct |
31 |
Correct |
86 ms |
59716 KB |
Output is correct |
32 |
Correct |
87 ms |
59596 KB |
Output is correct |
33 |
Correct |
102 ms |
64464 KB |
Output is correct |
34 |
Correct |
102 ms |
64528 KB |
Output is correct |
35 |
Correct |
106 ms |
64544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
58996 KB |
Output is correct |
2 |
Correct |
92 ms |
59640 KB |
Output is correct |
3 |
Correct |
88 ms |
59628 KB |
Output is correct |
4 |
Correct |
88 ms |
59640 KB |
Output is correct |
5 |
Execution timed out |
5058 ms |
81148 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
58964 KB |
Output is correct |
2 |
Correct |
93 ms |
64400 KB |
Output is correct |
3 |
Correct |
96 ms |
64468 KB |
Output is correct |
4 |
Correct |
98 ms |
64464 KB |
Output is correct |
5 |
Execution timed out |
5033 ms |
197552 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
58928 KB |
Output is correct |
2 |
Correct |
25 ms |
58988 KB |
Output is correct |
3 |
Correct |
25 ms |
58956 KB |
Output is correct |
4 |
Correct |
26 ms |
59060 KB |
Output is correct |
5 |
Correct |
86 ms |
63896 KB |
Output is correct |
6 |
Correct |
106 ms |
64024 KB |
Output is correct |
7 |
Correct |
96 ms |
62920 KB |
Output is correct |
8 |
Correct |
119 ms |
64392 KB |
Output is correct |
9 |
Correct |
110 ms |
64344 KB |
Output is correct |
10 |
Correct |
125 ms |
64432 KB |
Output is correct |
11 |
Correct |
135 ms |
64548 KB |
Output is correct |
12 |
Correct |
112 ms |
64328 KB |
Output is correct |
13 |
Correct |
104 ms |
64508 KB |
Output is correct |
14 |
Correct |
99 ms |
64460 KB |
Output is correct |
15 |
Correct |
103 ms |
64332 KB |
Output is correct |
16 |
Correct |
109 ms |
64432 KB |
Output is correct |
17 |
Correct |
105 ms |
64336 KB |
Output is correct |
18 |
Correct |
101 ms |
64324 KB |
Output is correct |
19 |
Correct |
130 ms |
64412 KB |
Output is correct |
20 |
Correct |
120 ms |
64312 KB |
Output is correct |
21 |
Correct |
114 ms |
64428 KB |
Output is correct |
22 |
Correct |
108 ms |
64428 KB |
Output is correct |
23 |
Correct |
39 ms |
64312 KB |
Output is correct |
24 |
Correct |
109 ms |
64384 KB |
Output is correct |
25 |
Correct |
94 ms |
64412 KB |
Output is correct |
26 |
Correct |
35 ms |
62452 KB |
Output is correct |
27 |
Correct |
36 ms |
63844 KB |
Output is correct |
28 |
Correct |
57 ms |
64416 KB |
Output is correct |
29 |
Correct |
66 ms |
64304 KB |
Output is correct |
30 |
Correct |
98 ms |
59768 KB |
Output is correct |
31 |
Correct |
86 ms |
59716 KB |
Output is correct |
32 |
Correct |
87 ms |
59596 KB |
Output is correct |
33 |
Correct |
102 ms |
64464 KB |
Output is correct |
34 |
Correct |
102 ms |
64528 KB |
Output is correct |
35 |
Correct |
106 ms |
64544 KB |
Output is correct |
36 |
Correct |
27 ms |
58996 KB |
Output is correct |
37 |
Correct |
92 ms |
59640 KB |
Output is correct |
38 |
Correct |
88 ms |
59628 KB |
Output is correct |
39 |
Correct |
88 ms |
59640 KB |
Output is correct |
40 |
Execution timed out |
5058 ms |
81148 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |