#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N, M, Q;
vector<pii> adj[MAXN+10];
pii A[MAXN+10];
struct SEG
{
ll tree[MAXN*4+10];
void init()
{
fill(tree, tree+MAXN*4+10, 0);
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
if(l<=tl && tr<=r)
{
tree[node]+=k;
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
}
ll query(int node, int tl, int tr, int k)
{
if(tl==tr) return tree[node];
int mid=tl+tr>>1;
if(k<=mid) return tree[node]+query(node*2, tl, mid ,k);
else return tree[node]+query(node*2+1, mid+1, tr, k);
}
}seg;
int L[MAXN+10], R[MAXN+10], dep[MAXN+10], par[MAXN+10][30], cnt, P[MAXN+10];
void dfs(int now, int bef, int d)
{
L[now]=++cnt;
par[now][0]=bef;
dep[now]=d;
for(auto [nxt, e] : adj[now])
{
if(nxt==bef) continue;
P[e]=nxt;
dfs(nxt, now, d+1);
}
R[now]=cnt;
}
int lca(int u, int v)
{
if(dep[u]>dep[v]) swap(u, v);
for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
if(u==v) return u;
for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
return par[u][0];
}
int C[MAXN+10];
pii B[MAXN+10];
pii D[MAXN+10];
int lo[MAXN+10], hi[MAXN+10];
int E[MAXN+10];
ll f(int p)
{
int u=B[p].first, v=B[p].second, w=C[p];
return seg.query(1, 1, N, L[u])+seg.query(1, 1, N, L[v])-2*seg.query(1, 1, N, L[w]);
}
int main()
{
scanf("%d%d%d", &N, &M, &Q);
for(int i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for(int i=1; i<=M; i++) scanf("%d%d", &A[i].second, &A[i].first);
dfs(1, 1, 1);
for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];
for(int i=1; i<=Q; i++) scanf("%d%d%d%d", &B[i].first, &B[i].second, &D[i].first, &D[i].second), C[i]=lca(B[i].first, B[i].second);
sort(A+1, A+M+1);
for(int i=1; i<=Q; i++) lo[i]=0, hi[i]=M+1;
while(1)
{
vector<pii> V;
for(int i=1; i<=Q; i++)
{
if(lo[i]+1<hi[i])
{
V.push_back({lo[i]+hi[i]>>1, i});
}
}
if(V.empty()) break;
sort(V.begin(), V.end());
seg.init();
int pt=1;
for(auto it : V)
{
for(; pt<=M && pt<=it.first; pt++)
{
seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], A[pt].first);
}
//printf("??%d %d %lld %d\n", it.first, it.second, f(it.second), D[it.second].second);
if(f(it.second)>D[it.second].second) hi[it.second]=it.first;
else lo[it.second]=it.first;
}
}
seg.init();
int pt=1;
vector<pii> V;
for(int i=1; i<=Q; i++) V.push_back({lo[i], i});
sort(V.begin(), V.end());
for(auto it : V)
{
for(; pt<=M && pt<=it.first; pt++)
{
seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], 1);
}
E[it.second]=f(it.second);
}
for(; pt<=M; pt++) seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], 1);
for(int i=1; i<=Q; i++)
{
//printf("%d %d %d\n", lo[i], f(i), E[i]);
printf("%lld\n", max(-1ll, D[i].first-f(i)+E[i]));
}
}
Compilation message
currencies.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
currencies.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid=tl+tr>>1;
| ~~^~~
currencies.cpp: In member function 'll SEG::query(int, int, int, int)':
currencies.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid=tl+tr>>1;
| ~~^~~
currencies.cpp: In function 'int main()':
currencies.cpp:105:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | V.push_back({lo[i]+hi[i]>>1, i});
| ~~~~~^~~~~~
currencies.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d%d", &N, &M, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
currencies.cpp:88:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | for(int i=1; i<=M; i++) scanf("%d%d", &A[i].second, &A[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:93:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | for(int i=1; i<=Q; i++) scanf("%d%d%d%d", &B[i].first, &B[i].second, &D[i].first, &D[i].second), C[i]=lca(B[i].first, B[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5844 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
6292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
6468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5844 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
