Tree/Jump_on_tree.test.cpp

• View this file on GitHub
• Last update: 2025-06-11 15:37:14+07:00
• Problem: https://judge.yosupo.jp/problem/jump_on_tree

Depends on

• Tree/Tree/BinaryLifting.h
• template.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/jump_on_tree"

#include "../template.h"
#include "Tree/BinaryLifting.h"

void solve() {
    int n, q; cin >> n >> q;
    BinLift binLift(n);
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        binLift.addEdge(u, v);
    }
    binLift.dfs(0, -1);
    while (q--) {
        int s, t, i; cin >> s >> t >> i;
        cout << binLift.jump(s, t, i) << '\n';
    }
}

#line 1 "Tree/Jump_on_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/jump_on_tree"

#line 2 "template.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);
    // int t; cin >> t;
    // while(t--)
        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "Tree/Tree/BinaryLifting.h"

class BinLift {
public:
    int n;
    vector<vector<int>> tree, up;
    vector<int> lg, h;

    BinLift() {}
    BinLift(int n): n(n), tree(n), up(n, vector<int>(20)), lg(20), h(n) {}

    void dfs(int u, int p) {
        for(int v : tree[u]) {
            if(v == p) continue;
            up[v][0] = u;
            h[v] = h[u] + 1;
            for(int j = 1; j < 20; j++)
            up[v][j] = up[up[v][j-1]][j-1];
            dfs(v, u);
        }
    }

    void addEdge(int u, int v) {
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }

    int jump(int u, int v, int i) {
        int t = lca(u, v);
        int diff1 = h[u]-h[t];
        int diff2 = h[v]-h[t];
        if (i > diff1 + diff2) return -1;
        if (i <= diff1) return ancestor_k(u, i);
        else {
            int step = i-diff1;
            return ancestor_k(v, diff2-step);
        }
    }

    int lca(int u, int v) {
        if(h[u] < h[v]) swap(u, v);
        int k = h[u]-h[v];
        u = ancestor_k(u, k);
        if(u == v) return u;

        k = __lg(h[u]);
        for(int j = k; j >= 0; j--) {
            if(up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }

    int ancestor_k(int u, int k) {
        for(int j = 0; (1 << j) <= k; j++) {
            if(k >> j & 1)
                u = up[u][j];
        }
        return u;
    }
};
#line 5 "Tree/Jump_on_tree.test.cpp"

void solve() {
    int n, q; cin >> n >> q;
    BinLift binLift(n);
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        binLift.addEdge(u, v);
    }
    binLift.dfs(0, -1);
    while (q--) {
        int s, t, i; cin >> s >> t >> i;
        cout << binLift.jump(s, t, i) << '\n';
    }
}

Back to top page