1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using pii = pair<int, int>;
6

7
class lca {
8
    vector<int> depth;
9
    vector<ll> dis;
10
    vector<vector<int>> pa;// 本质为步长为2^i的父亲数组
11

12
public:
13
    lca(const vector<vector<int>>& edges) {
14
        int n = edges.size() + 1;
15
        int m = bit_width((unsigned) n);
16
        vector<vector<pii>> g(n);
17
        depth.resize(n);
18
        dis.resize(n);
19
        pa.resize(n, vector<int>(m, -1));
20

21
        for (auto& e : edges) {
22
            int x = e[0], y = e[1], w = e[2];
23
            g[x].emplace_back(y, w);
24
            g[y].emplace_back(x, w);
25
        }
26

27
        auto dfs = [&](auto&& dfs, int x, int fa) -> void {
28
            pa[x][0] = fa;
29
            for (auto& [y, w] : g[x]) {
30
                if (y != fa) {
31
                    depth[y] = depth[x] + 1;
32
                    dis[y] = dis[x] + w;
33
                    pa[y][0] = x;
34
                    dfs(dfs, y, x);
35
                }
36
            }
37
        };
38
        dfs(dfs, 0, -1);
39

40
        for (int i = 0; i < m - 1; ++i) {
41
            for (int x = 0; x < n; ++x) {
42
                int p = pa[x][i];
43
                if (p != -1) {
44
                    pa[x][i + 1] = pa[p][i];
45
                }
46
            }
47
        }
48
    }
49

50
    int get_kth_anc(int node, int k) {
51
        for (; k > 0 && node >= 0; k &= k - 1) {
52
            node = pa[node][countr_zero((unsigned) k)];
53
        }
54
        return node;
55
    }
56

57
    int get_lca(int x, int y) {
58
        if (depth[x] > depth[y]) swap(x, y);
59

60
        y = get_kth_anc(y, depth[y] - depth[x]);
61
        if (y == x) return x;
62

63
        for (int i = pa.size() - 1; i >= 0; --i) {
64
            int px = pa[x][i], py = pa[y][i];
65
            if (px != py) {
66
                x = px;
67
                y = py;
68
            }
69
        }
70
        return pa[x][0];
71
    }
72
};