#include<bits/stdc++.h>
#define int long long
const int MaxN = 1e5 + 10;
const int MaxBit = 20;
int n,m,k,timeIn[MaxN + 1],timeOut[MaxN + 1],parent[MaxN + 1][MaxBit + 1],timer = 0;
std::vector<int> adj[MaxN + 1];
struct FenwickTree{
std::vector<long long> bit;
FenwickTree(int n) : bit(n + 1,0){
}
void update(int idx,long long val){
for(int i = idx;i < (int)bit.size();i += (i & (-i))){
bit[i] += val;
}
}
void updateRange(int l,int r,long long val){
// if(!(r >= 1 && r <= n)){
// r = r;
// assert(false);
// }
// assert(l >= 1 && l <= n);
// assert(r >= 1 && r <= n);
update(l,val);
update(r + 1,-val);
}
long long getSum(int idx){
long long ans =0 ;
for(int i = idx;i > 0;i -= (i & (-i))){
ans += bit[i];
}
return ans;
}
};
struct Checkpoint{
int u;
long long coin;
Checkpoint() : u(0),coin(0){
}
bool operator < (const Checkpoint &other){
return (coin < other.coin);
}
}point[MaxN + 1];
struct Query{
int gold,silver,u,v,lo,hi,mid,ans,index;
Query() :gold(0),silver(0),u(0),v(0),lo(0),hi(0),mid(0),ans(0),index(0){
}
bool operator < (const Query &other){
return (mid < other.mid);
}
}query[MaxN + 1];
struct Edge{
int u,v,w;
bool operator < (const Edge &other){
return (w < other.w);
}
};
std::vector<Edge> edge;
void readData(){
std::cin >> n >> m >> k;
edge.push_back({0,0,0});
for(int i = 1;i < n;++i){
int a,b;
std::cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
edge.push_back({a,b,0});
}
for(int i = 1;i <= m;++i){
int p,c;
std::cin >> p >> c;
edge.push_back({edge[p].u,edge[p].v,c});
}
std::sort(edge.begin(),edge.end());
for(int i = 1;i <= k;++i){
std::cin >> query[i].u >> query[i].v >> query[i].gold >> query[i].silver;
query[i].index = i;
query[i].lo = n - 1,query[i].hi = (int)edge.size() - 1;
query[i].mid = (query[i].lo + query[i].hi) / 2;
}
}
void dfs(int u = 1,int par = 1){
timeIn[u] = ++timer;
parent[u][0] = par;
for(int v : adj[u]){
if(v == par){
continue;
}
dfs(v,u);
}
timeOut[u] = timer;
}
void binaryLift(){
for(int i = 1;i <= MaxBit;++i){
for(int j = 1;j <= n;++j){
parent[j][i] = parent[parent[j][i - 1]][i - 1];
}
}
}
bool isAncestor(int u,int v){
return (timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v]) ;
}
int lca(int u,int v){
if(isAncestor(u,v)){
return u;
}
if(isAncestor(v,u)){
return v;
}
for(int i = MaxBit;i >= 0;--i){
if(!isAncestor(parent[u][i],v)){
u = parent[u][i];
}
}
return parent[u][0];
}
void parallelBinarySearch(){
for(Edge &e : edge){
if(!isAncestor(e.u,e.v)){
std::swap(e.u,e.v);
}
}
for(int i = 1;i <= 20;++i){
int it = n - 1;
FenwickTree ft(n);
std::sort(query + 1,query + k + 1);
std::function<long long(int,int)> getSum = [&](int u,int v){
int l = lca(u,v);
return ft.getSum(timeIn[u]) + ft.getSum(timeIn[v]) - ft.getSum(timeIn[l]);
};
for(int j = 1;j <= k;++j){
if(query[j].lo > query[j].hi){
continue;
}
while(it < query[j].mid){
++it;
// if(it > m && it < (int)edge.size()){
// it = it;
// }
// assert(it > m && it < (int)edge.size());
// std::cerr << edge[it].v << "\n";
ft.updateRange(timeIn[edge[it].v],timeOut[edge[it].v],edge[it].w);
}
long long s = getSum(query[j].u,query[j].v);
// if(s > 16){
// std::cerr << s << "\n";
// }
if(s <= query[j].silver){
query[j].ans = query[j].mid;
query[j].lo = query[j].mid + 1;
}else{
query[j].hi = query[j].mid - 1;
}
query[j].mid = (query[j].lo + query[j].hi) / 2;
}
}
}
void answer(){
std::vector<int> ans(k + 1);
std::sort(query + 1,query + k + 1,[](const Query &a,const Query &b){
return a.ans < b.ans;
});
int it = (int)edge.size();
FenwickTree ft(n);
for(int i = k;i >= 1;--i){
std::function<long long(int,int)>getSum = [&](int u,int v){
int l = lca(u,v);
return ft.getSum(timeIn[u]) + ft.getSum(timeIn[v]) - ft.getSum(timeIn[l]);
};
// std::cerr << query[i].ans << "\n";
while(it > query[i].ans + 1){
--it;
// std::cerr << edge[it].v << "\n";
ft.updateRange(timeIn[edge[it].v],timeOut[edge[it].v],1);
}
long long s = getSum(query[i].u,query[i].v);
if(s > query[i].gold){
ans[query[i].index] = -1;
}else{
ans[query[i].index] = query[i].gold - s;
}
}
for(int i = 1;i <= k;++i){
std::cout << ans[i] << "\n";
}
}
signed main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
dfs();
binaryLift();
parallelBinarySearch();
answer();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15096 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14936 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
14936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15096 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14936 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
14936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
