So, a few months ago, I was working on Euler Tour from the usaco guide website. There, they explained how you could compress a tree into an array of start[] and end[] arrays to build a segment tree on top of it. However, with LCA (least common ancestor, they built a RMQ (range minimum query) segtree off of the full inorder traversal of the tree, which confused me greatly. After all, in the examples of summing subtrees and updating vertexes, we hadn't needed to do that. Additionally, I was still greatly uncomfortable with changing the size of the segtree, and a segtree with 2 * (2n-1) memory (I use the iterative version) pissed me off. I gave up and went back to dynamic programming.

Yesterday, however, I returned. The most annoying thing, in my opinion, was how the start[] and end[] arrays were combined so the segtree could be built, and there were two ways to do the euler tour I had to remember. Indeed, in my code I wrote the following:

N = euler.size();  //do not do this

So, I present a way to build the segtree off of only the start[] array. To understand this, make sure you know point update range sum segtree (I don't know fenwick tree/BIT but it likely also works here) and how to solve, say, Subtree Queries on CSES, or have read the corresponding section (18.2) in CPH.

#include <bits/stdc++.h>
 
using namespace std;
vector<vector<int>> tree;
vector<int> start;
vector<int> stop;
vector<int> par;
vector<int> depth;
vector<int> seg;
int n;
int euler = 0;
void dfs(int v, int d) {
    start[v] = euler;
    depth[v] = d;
    euler++;
    for (int x : tree[v]) {
        dfs(x, d + 1);
    }
    stop[v] = euler;
}
int comp(int u, int v) {
    return depth[v] < depth[u] ? v : u;
}
void init() {
    seg.resize(2 * n);
    for (int i = 0; i < n; i++) {
        seg[start[i] + n] = i;
    }
    for (int i = n - 1; i > 0; i--) {
        seg[i] = comp(seg[i * 2], seg[i * 2 + 1]);
    }
}
int query(int l, int r) {
    int ans = seg[l + n];
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l & 1) { ans = comp(ans, seg[l++]); }
        if (r & 1) { ans = comp(ans, seg[--r]); }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int q; cin >> n >> q;
    tree.resize(n);
    start.resize(n);
    stop.resize(n);
    depth.resize(n);
    par.resize(n);
    for (int i = 1; i < n; i++) {
        int b; cin >> b; b--;
        tree[b].push_back(i);
        par[i] = b;
    }
    dfs(0, 0);
    init();
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b; a--; b--;
        if (start[b] < start[a]) { swap(a, b); }
        if (stop[a] >= stop[b]) { cout << a+1 << "\n"; continue; }
        cout << par[query(start[a], start[b] + 1)] + 1 << "\n";
    }
}

To see why this works, let's take a look at an example.

The corresponding array we build off of (and the depths):

[1, 2, 5, 6, 3, 4, 7]
[0, 1, 2, 2, 1, 1, 2]

Essentially what we are building off of is the first array, where the nodes are ordered by when we first meet them in the dfs traversal. Then: To find the LCA of two nodes, if any of the two is not within the others subtree, then the LCA is the parent node of the RMQ (based on depth, of course) in the range between the two. The parent node will not be present in this range, because it must have already been visited before. Proof of correctness is left to the reader, as always, for the author is forever typing at 12:22 am (I am sure, however, the proof is simple).

So, is this any better than before? We built on a segtree of half the size, after all.

Well, not really. Because segtree operations take O(log N) after processing, actually, we are reducing the time per query by O(1). And likely because we are adding a vector to track the parent of each vertex, it isn't any faster. Memory isn't any better, either.

So what's the use?

Now, at least, there aren't two ideas for euler tour running inside my head. I just understand that I can use start[] and stop[] arrays for this. It's mostly for simplicity, really. And because I'm doing usaco guide, I probably won't learn binary lifting until later, as it's in platinum.

This was just a fun thing to think about and do. Open to any code simplifications and blog criticisms! It's my first time writing one. Thanks to iframe_ for helping optimize it, and thank you for reading!