#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll long long
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
const ll mod = 1e9 + 7;
const ll mod2 = 1e9 + 6;
const ll INF = 2e18;
const int INT_INF = 1e9 + 11;
long long binpow(long long base, long long power, long long mod) {
if (base == 0) return 0;
if (base == 1) return 1;
if (power <= 0) return 1;
long long multiplier = (power % 2 == 0 ? 1 : base) % mod;
return (multiplier * binpow((base * base) % mod, power / 2, mod)) % mod;
}
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a % b);
}
const int N = 1e5 + 5;
const int LOGN = 18;
vector<int> adj[N];
pair<int, int> edges[N];
pair<int, int> checkpoints[N]; // First is cost and second is index
int binlift[N][LOGN];
int in[N], out[N];
int timer = 0;
void fill_binlift(int node, int prev){
binlift[node][0] = prev;
for(int lift = 1; lift < LOGN; lift++){
int half_way = binlift[node][lift - 1];
if(half_way == -1) break;
binlift[node][lift] = binlift[half_way][lift - 1];
}
}
void euler_tour(int node, int prev = -1){
in[node] = ++timer;
fill_binlift(node, prev);
for(int v : adj[node]){
if(v == prev) continue;
euler_tour(v, node);
}
out[node] = timer;
}
bool is_ancestor(int parent, int child){
assert(parent != -1 && child != -1);
return (in[parent] <= in[child] && out[parent] >= out[child]);
}
int lca(int a, int b){
assert(a != -1 && b != -1);
if(in[a] > in[b]) swap(a, b);
if(is_ancestor(a, b)) return a;
int cur = b;
for(int lift = LOGN - 1; lift >= 0; lift--){
int lifted = binlift[cur][lift];
if(lifted == -1) continue;
if(is_ancestor(lifted, a)) continue;
cur = lifted;
}
// Cur is one away
return binlift[cur][0];
}
void reorder_edges(){
for(int i = 1; i < N; i++){
if(edges[i].first == 0) break;
if(is_ancestor(edges[i].second, edges[i].first)) swap(edges[i].first, edges[i].second);
}
}
struct Fenwick{
int n;
vector<ll> tree;
Fenwick(int n = 0) : n(n), tree(n, 0){
}
void update(int pos, ll val){
for(int i = pos; i < n; i += (i & -i)) tree[i] += val;
}
ll get(int pos){
ll ans = 0;
for(int i = pos; i > 0; i -= (i & -i)) ans += tree[i];
return ans;
}
};
struct Query{
int start, end;
ll gold, silver;
Query(int start = 0, int end = 0, ll gold = 0, ll silver = 0) : start(start), end(end), gold(gold), silver(silver){
}
};
void Run(){
for(int i = 0; i < N; i++) for(int j = 0; j < LOGN; j++) binlift[i][j] = -1;
int n, m, q; cin >> n >> m >> q;
for(int i = 1; i <= n - 1; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
edges[i] = {a, b};
}
euler_tour(1);
reorder_edges(); // To ensure that the ancestor is always the first element
Fenwick checkpoint_tree(n + 3); // Holds number of checkpoints from root to this node
for(int i = 1; i <= m; i++){
int p; ll c;
cin >> p >> c;
int l = in[edges[p].second];
int r = out[edges[p].second];
checkpoint_tree.update(l, 1);
checkpoint_tree.update(r + 1, -1);
checkpoints[i] = {c, p};
}
sort(checkpoints + 1, checkpoints + m + 1);
vector<Query> queries(q);
for(int i = 0; i < q; i++){
ll s, t, gold, sil;
cin >> s >> t >> gold >> sil;
queries[i] = Query(s, t, gold, sil);
}
vector<int> left(q, 0);
vector<int> right(q, m);
vector<int> ans(q, 0);
int times = LOGN + 1;
while(times--){
// Clearing
Fenwick silver_tree(n + 3); // Holds sum of silver used
vector<vector<int>> candidates(m + 1); // Hold candidates for each mid
// Update mid for every intervals
for(int i = 0; i < q; i++){
if(left[i] < right[i]){
int mid = (left[i] + right[i] + 1) / 2;
candidates[mid].push_back(i);
} else{
ans[i] = left[i];
}
}
// Events: update the edges
for(int mid = 0; mid <= m; mid++){
// Update
if(mid != 0){
pair<int, int> edge = edges[checkpoints[mid].second];
int l = in[edge.second];
int r = out[edge.second];
silver_tree.update(l, checkpoints[mid].first);
silver_tree.update(r + 1, -checkpoints[mid].first);
}
// Answer queries
for(int cand : candidates[mid]){
ll silver_used =
silver_tree.get(in[queries[cand].start])
+ silver_tree.get(in[queries[cand].end]);
- 2 * silver_tree.get(in[lca(queries[cand].start, queries[cand].end)]);
if(silver_used > queries[cand].silver){
right[cand] = mid - 1;
} else left[cand] = mid;
}
}
}
vector<vector<int>> candidates(m + 1);
vector<ll> ans_queries(q);
for(int i = 0; i < q; i++) candidates[ans[i]].push_back(i);
// Answer each query
Fenwick active_tree(n + 3);
for(int mid = 0; mid <= m; mid++){
// Update
if(mid != 0){
pair<int, int> edge = edges[checkpoints[mid].second];
int l = in[edge.second];
int r = out[edge.second];
active_tree.update(l, 1);
active_tree.update(r + 1, -1);
}
// Answer queries
for(int cand : candidates[mid]){
ll gold_saved =
active_tree.get(in[queries[cand].start])
+ active_tree.get(in[queries[cand].end]);
- 2 * active_tree.get(in[lca(queries[cand].start, queries[cand].end)]);
ll checkpoints_on_the_way =
checkpoint_tree.get(in[queries[cand].start])
+ checkpoint_tree.get(in[queries[cand].end]);
- 2 * checkpoint_tree.get(in[lca(queries[cand].start, queries[cand].end)]);
ll remaining_gold = queries[cand].gold + gold_saved - checkpoints_on_the_way;
if(remaining_gold < 0){
ans_queries[cand] = -1;
} else{
ans_queries[cand] = remaining_gold;
}
}
}
for(int i = 0; i < q; i++) cout << ans_queries[i] << "\n";
}
int main(){
//freopen("CIRSSTR.INP", "r", stdin);
//freopen("CIRSSTR.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int test = 1;
//cin >> test;
// Measuring running time (breaks when manual input)
//auto time_start = clock();
while(test--) Run();
//auto time_end = clock();
//cerr << "Time taken: " << time_end - time_start << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |