Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- const int inf = 1e18;
- const int LG = 17;
- const int N = 1e5 + 1;
- int up[LG][N] = {}, d[N];
- int up_min[LG][N];
- int t = 0;
- vector<vector<pair<int,int>>> gr;
- void dfs(int v, int p) {
- for (int l = 1; l < LG; l++) {
- up[l][v] = up[l - 1][up[l - 1][v]];
- up_min[l][v] = min(up_min[l - 1][v], up_min[l - 1][up[l - 1][v]]);
- }
- if (p == -1) {
- d[v] = 0;
- up[0][v] = 0;
- up_min[0][v] = inf;
- }
- else {
- d[v] = d[p] + 1;
- }
- for (auto&& [u, w] : gr[v]) {
- if (u != p) {
- up[0][u] = v;
- up_min[0][u] = w;
- dfs(u, v);
- }
- }
- }
- int get_mn(int a, int b) {
- int ans = inf;
- if (a == b)return a;
- if (d[b] > d[a])swap(a, b);
- for (int i = LG - 1; i >= 0; i--) {
- if (d[up[i][a]] >= d[b]) {
- ans = min(ans, up_min[i][a]);
- a = up[i][a];
- }
- }
- if (a == b) return ans;
- for (int i = LG - 1; i >= 0; i--) {
- if (up[i][a] != up[i][b]) {
- ans = min(ans, min(up_min[i][a], up_min[i][b]));
- a = up[i][a], b = up[i][b];
- }
- }
- return min(ans, min(up_min[0][b],up_min[0][a]));
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, m; cin >> n;
- gr.resize(n);
- for (int i = 1; i < n; i++) {
- int v, w; cin >> v >> w;
- v--;
- gr[v].push_back({ i,w });
- gr[i].push_back({ v,w });
- }
- for (int i = 0; i < LG; i++) {
- for (int j = 0; j < n; j++) {
- up_min[i][j] = inf;
- }
- }
- dfs(0, -1);
- int q; cin >> q;
- for (int i = 0; i < q; i++) {
- int a, b;
- cin >> a >> b;
- a--, b--;
- cout << get_mn(a, b) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement