Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/extc++.h>
- #define int int64_t
- using namespace std;
- using namespace __gnu_pbds;
- const int N = 1e5 + 1;
- const int L = 17;
- int n, timer;
- array<int, N> tin, tout;
- array<array<int, N>, L> up, mn;
- array<vector<pair<int, int>>, N> g;
- void dfs(int v = 0, int p = -1) {
- tin[v] = timer++;
- for (int l = 1; l < L; l++) {
- up[l][v] = up[l - 1][up[l - 1][v]];
- mn[l][v] = min(mn[l - 1][v], mn[l - 1][up[l - 1][v]]);
- }
- for (auto [u, w] : g[v]) {
- if (u != p) {
- up[0][u] = v;
- mn[0][u] = w;
- dfs(u, v);
- }
- }
- tout[v] = timer++;
- }
- bool ancestor(int v, int u) {
- return tin[v] <= tin[u] && tout[v] >= tout[u];
- }
- int lca(int v, int u) {
- if (ancestor(v, u)) {
- return v;
- }
- if (ancestor(u, v)) {
- return u;
- }
- for (int l = L - 1; l >= 0; l--) {
- if (!ancestor(up[l][v], u)) {
- v = up[l][v];
- }
- }
- return up[0][v];
- }
- int min_edge(int v, int u) {
- int cur = lca(v, u);
- int ans = numeric_limits<int>::max();
- for (int l = L - 1; l >= 0; l--) {
- if (!ancestor(up[l][v], cur)) {
- ans = min(ans, mn[l][v]);
- v = up[l][v];
- }
- if (!ancestor(up[l][u], cur)) {
- ans = min(ans, mn[l][u]);
- u = up[l][u];
- }
- }
- if (!ancestor(v, cur)) {
- ans = min(ans, mn[0][v]);
- }
- if (!ancestor(u, cur)) {
- ans = min(ans, mn[0][u]);
- }
- return ans;
- }
- int32_t main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int v = 1; v < n; v++) {
- int u;
- cin >> u;
- u--;
- int w;
- cin >> w;
- g[u].emplace_back(v, w);
- g[v].emplace_back(u, w);
- }
- dfs();
- int q;
- cin >> q;
- while (q--) {
- int v, u;
- cin >> v >> u;
- v--, u--;
- cout << min_edge(v, u) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment