#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
struct FenwickTree{
int n; vector<int> t;
void init(int _n){
n=_n;
t.assign(n+1, 0);
}
void update(int pos, int val){
for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
}
void update(int l, int r, int val){
update(l, val);
update(r+1, -val);
}
int get(int pos){
int ans=0;
for (int i=pos; i; i-=i&(-i)) ans+=t[i];
return ans;
}
} bit;
struct nigga{
int s, t, x, y;
nigga(int a=0, int b=0, int c=0, int d=0): s(a), t(b), x(c), y(d){};
};
const int N=1e5+1, LG=17;
int n, m, q, tdfs, tin[N], tout[N], up[N][LG], dep[N], l[N], r[N], ans[N];
vector<int> g[N], vv[N];
nigga a[N];
void dfs(int u){
tin[u]=tout[u]=++tdfs;
dep[u]=dep[up[u][0]]+1;
for (int v:g[u]) if (v!=up[u][0]){
up[v][0]=u;
for (int k=1; k<LG; ++k) up[v][k]=up[up[v][k-1]][k-1];
dfs(v);
}
}
int lca(int u, int v){
if (dep[u]!=dep[v]){
if (dep[u]<dep[v]) swap(u, v);
int d=dep[u]-dep[v];
for (int k=0; k<LG; ++k) if (d>>k&1) u=up[u][k];
}
if (u==v) return u;
for (int k=LG-1; k>=0; --k) if (up[u][k]!=up[v][k]) u=up[u][k], v=up[v][k];
return up[u][0];
}
int dis(int u, int v){
return dep[u]+dep[v]-(dep[lca(u, v)]<<1);
}
void solve(int tc){
// cout << "Case #" << tc << ": ";
cin >> n >> m >> q;
vector<pair<int, int>> edges;
for (int i=1; i<n; ++i){
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
edges.emplace_back(x, y);
}
dfs(1);
vector<pair<int, int>> pts;
vector<int> vals{0};
for (int i=1; i<=m; ++i){
int p, c; cin >> p >> c; --p;
vals.push_back(c);
int x=edges[p].first, y=edges[p].second;
if (tin[x]>tin[y]) swap(x, y);
pts.emplace_back(c, y);
}
sort(all(pts));
sort(all(vals)); vals.resize(unique(all(vals))-vals.begin());
for (int i=1; i<=q; ++i){
cin >> a[i].s >> a[i].t >> a[i].x >> a[i].y;
l[i]=0, r[i]=sz(vals)-1;
}
for (int rep=0; rep<LG; ++rep){
for (int i=1; i<=q; ++i) if (l[i]<=r[i]) vv[(l[i]+r[i])>>1].push_back(i);
bit.init(n); bit.init(n);
for (int i=0, j=0; i<sz(vals); ++i){
while (j<sz(pts) && pts[j].first==vals[i]){
bit.update(tin[pts[j].second], tout[pts[j].second], pts[j].first);
++j;
}
for (int k:vv[i]){
int u=a[k].s, v=a[k].t, w=lca(u, v);
int sum_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
if (sum_silver<=a[k].y) l[k]=i+1;
else r[k]=i-1;
}
vv[i].clear();
}
}
for (int i=1; i<=q; ++i) vv[r[i]].push_back(i);
bit.init(n);
for (int i=0, j=0; i<sz(vals); ++i){
while (j<sz(pts) && pts[j].first==vals[i]){
bit.update(tin[pts[j].second], tout[pts[j].second], 1);
++j;
}
for (int k:vv[i]){
int u=a[k].s, v=a[k].t, w=lca(u, v);
int cnt_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
int cnt_gold=dis(u, v)-cnt_silver;
ans[k]=cnt_gold<=a[k].x?cnt_gold:-1;
}
vv[i].clear();
}
for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve(i);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
8160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
8160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
