Company Queries II

#include <iostream>
#include <vector>

using namespace std;

void euler_dfs(const vector<vector<int>> &adj, int node, int d, vector<int> &first_occur, vector<int> &depth, vector<int> &euler_tour) {
    if (first_occur[node] == -1) {
        first_occur[node] = euler_tour.size();
    }
    depth[node] = d;
    euler_tour.push_back(node);

    for (int child : adj[node]) {
        euler_dfs(adj, child, d + 1, first_occur, depth, euler_tour);
        euler_tour.push_back(node);
    }
}


int main() {
    int n, q;
    cin >> n >> q;

    // Read tree
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; ++i) {
        int parent;
        cin >> parent;
        adj[parent - 1].push_back(i);
    }

    vector<int> first_occur(n, -1);
    vector<int> euler_tour;
    vector<int> depth(n, 0);

    euler_dfs(adj, 0, 1, first_occur, depth, euler_tour);

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;

        // Ensure a is before b in the Euler tour
        if (first_occur[a] > first_occur[b])
            swap(a, b);

        // Find LCA by checking the minimum depth in the range
        int lca = a;
        for (int j = first_occur[a]; j <= first_occur[b]; ++j) {
            int node = euler_tour[j];
            if (depth[node] < depth[lca])
                lca = euler_tour[j];
        }
        cout << lca + 1 << endl;
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED