[Working In Progress] Euler Tour Trick + LCA + HLD Template

struct EulerTour
{
    int N;
    vector<int> SZ, H;
    vector<pair<int, int>> ETT;
    vector<vector<int>> childs, sp;
    vector<vector<pair<int, int>>> rngs;
    EulerTour(){};
    EulerTour(vector<vector<int>> G, int root = 0)
        : N(G.size()), SZ(N), H(N), ETT(N), childs(N),
          sp(bit_width((unsigned)N), vector<int>(N)), rngs(N)
    {
        function<void(int, int, int)> dfs = [&](int a, int p, int h)
        {
            sp[0][a] = p, SZ[a] = 1, H[a] = h;
            for (auto &b : G[a])
                if (b != p)
                {
                    dfs(b, a, h + 1);
                    SZ[a] += SZ[b];
                    if (G[a][0] == p || SZ[G[a][0]] < SZ[b])
                        swap(b, G[a][0]);
                }
        };
        dfs(root, -1, 0);
        for (int i = 1; i < (int)sp.size(); ++i)
            for (int j = 0; j < N; ++j)
                if (sp[i - 1][j] != -1)
                    sp[i][j] = sp[i - 1][sp[i - 1][j]];
 
        int gidx = 0;
        vector<pair<int, int>> rng;
        function<void(int)> ett = [&](int a)
        {
            if (rng.empty() || rng.back().second != gidx)
                rng.emplace_back(gidx, gidx + 1);
            else
                rng.back().second++;
 
            ETT[a].first = gidx++;
            rngs[a] = rng;
            for (int b : G[a])
                if (b != sp[0][a])
                    ett(b);
            ETT[a].second = gidx;
 
            if (rng.back().first + 1 == rng.back().second)
                rng.pop_back();
            else
                rng.back().second--;
        };
        ett(root);
    }
 
    int lca(int u, int v)
    {
        if (H[u] < H[v])
            swap(u, v);
        int hdiff = H[u] - H[v];
        for (int i = 0; i < (int)sp.size(); ++i)
            if (hdiff & (1 << i))
                u = sp[i][u];
        if (u == v)
            return u;
        for (int i = (int)sp.size() - 1; i >= 0; --i)
        {
            int pu = sp[i][u], pv = sp[i][v];
            if (pu != pv)
                u = pu, v = pv;
        }
        return sp[0][u];
    }
 
    pair<int, int> subtree(int a) { return ETT[a]; }
    vector<pair<int, int>> rootpath(int a) { return rngs[a]; }
    vector<pair<int, int>> path(int u, int v)
    {
        int r = ETT[lca(u, v)].first;
        vector<pair<int, int>> ret;
        for (auto [s, e] : rootpath(u))
            if (e + 1 >= r)
                ret.emplace_back(max(s, r), e);
        for (auto [s, e] : rootpath(v))
            if (e >= r)
                ret.emplace_back(max(s, r + 1), e);
        return ret;
    }
};

Sample Usage:

• Problem: https://www.acmicpc.net/problem/17429
• Code: https://www.acmicpc.net/source/share/29df4fc631d14b97ba84e21bea6a2d87