#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<vector<int>> g,jump;
vector<int> dep,dis,c;
int cost;
void dfs(int pre,int pos){
for(int i:g[pos]){
if(i==pre) continue;
jump[i][0]=pos;
dep[i]=dep[pos]+1;
dis[i]=dis[pos]+c[i];
dfs(pos,i);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
int diff=dep[x]-dep[y],cnt=0;
while(diff){
if(diff&1){
x=jump[x][cnt];
}
cnt++;
diff>>=1;
}
if(x==y) return x;
for(int i=19;i>=0;i--){
if(jump[x][i]!=jump[y][i]){
x=jump[x][i];
y=jump[y][i];
}
}
return jump[x][0];
}
int sol(int x,int y){
return dis[x]+dis[y]-2*dis[lca(x,y)];
}
signed main(){
int n,m,q;
cin>>n>>m>>q;
g.resize(n);
dep.resize(n);
dis.resize(n);
c.resize(n);
jump.resize(n,vector<int>(20));
vector<pii> ed(n-1);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
a--;
b--;
ed[i]={a,b};
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0,0);
while(m--){
int a,b;
cin>>a>>b;
cost=b;
a--;
pii e=ed[a];
if(dep[e.F]<dep[e.S]) swap(e.F,e.S);
c[e.F]++;
}
dfs(0,0);
//for(int i:dep) cout<<i<<' ';cout<<endl;
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
jump[j][i]=jump[jump[j][i-1]][i-1];
}
}
while(q--){
int s,t,x,y;
cin>>s>>t>>x>>y;
s--;
t--;
int tmp=sol(s,t);
//cout<<tmp<<endl;
tmp-=y/cost;
tmp=max(0LL,tmp);
x-=tmp;
if(x<0){
cout<<-1<<endl;
}
else cout<<x<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
6 ms |
1000 KB |
Output is correct |
3 |
Correct |
6 ms |
1116 KB |
Output is correct |
4 |
Correct |
7 ms |
1112 KB |
Output is correct |
5 |
Correct |
364 ms |
34552 KB |
Output is correct |
6 |
Correct |
327 ms |
25256 KB |
Output is correct |
7 |
Correct |
347 ms |
29516 KB |
Output is correct |
8 |
Correct |
275 ms |
30120 KB |
Output is correct |
9 |
Correct |
282 ms |
29764 KB |
Output is correct |
10 |
Correct |
398 ms |
35408 KB |
Output is correct |
11 |
Correct |
396 ms |
35668 KB |
Output is correct |
12 |
Correct |
385 ms |
35408 KB |
Output is correct |
13 |
Correct |
449 ms |
35528 KB |
Output is correct |
14 |
Correct |
388 ms |
35412 KB |
Output is correct |
15 |
Correct |
486 ms |
39912 KB |
Output is correct |
16 |
Correct |
471 ms |
40028 KB |
Output is correct |
17 |
Correct |
472 ms |
39512 KB |
Output is correct |
18 |
Correct |
447 ms |
35408 KB |
Output is correct |
19 |
Correct |
434 ms |
35156 KB |
Output is correct |
20 |
Correct |
440 ms |
35412 KB |
Output is correct |
21 |
Correct |
350 ms |
34904 KB |
Output is correct |
22 |
Correct |
350 ms |
35016 KB |
Output is correct |
23 |
Correct |
354 ms |
35420 KB |
Output is correct |
24 |
Correct |
349 ms |
35124 KB |
Output is correct |
25 |
Correct |
390 ms |
35832 KB |
Output is correct |
26 |
Correct |
380 ms |
35804 KB |
Output is correct |
27 |
Correct |
395 ms |
35700 KB |
Output is correct |
28 |
Correct |
348 ms |
35152 KB |
Output is correct |
29 |
Correct |
377 ms |
35412 KB |
Output is correct |
30 |
Correct |
419 ms |
35440 KB |
Output is correct |
31 |
Correct |
356 ms |
35284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |