[Hackerearth] RebelReach

 

Problem Link    : RebelReach
Category        : Graph, Binary Search
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
int n;
int q;
vector<vector<int>> graph;
vector<int> guards;
vector<vector<pii>> queries;
vector<int> arr;
vector<int> cumsum;
vector<int> ans;
 
void dfs(int u, int p) {
    arr.push_back(u);
    cumsum.push_back(guards[u] + (cumsum.size() ? cumsum.back() : 0));
    for (pii it : queries[u]) {
        int x = it.first;
        int lo = 0;
        int hi = arr.size() - 1;
        int id = arr.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            int sum = cumsum.back() - (mid - 1 >= 0 ? cumsum[mid - 1] : 0);
            if (sum <= x) {
                id = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        int sum = cumsum.back() - (id - 1 >= 0 ? cumsum[id - 1] : 0);
        ans[it.second] = arr[id];
        if (sum < x and id - 1 >= 0) {
            ans[it.second] = arr[id - 1];
        }
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    arr.pop_back();
    cumsum.pop_back();
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    guards.clear(); guards.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> guards[i];
    }
    cin >> q;
    queries.clear(); queries.resize(n + 1);
    for (int i = 0; i < q; i++) {
        int u, x;
        cin >> u >> x;
        queries[u].push_back(pii(x, i));
    }
    arr.clear();
    cumsum.clear();
    ans.clear(); ans.resize(q);
    dfs(1, 0);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}