Company Queries II

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;
#define ll long long
#define ull unsigned long long
#define vi vector<int>

void dfs_traversal(int node, vector<vi>& adj, vi& trav_node_id, vi& trav_depth, int depth) {

    // Inform the traversal on the node we are going through
    trav_node_id.push_back(node);
    trav_depth.push_back(depth);

    // If successors, dfs them ...
    for (int neighbor : adj[node]) {
        dfs_traversal(neighbor, adj, trav_node_id, trav_depth, depth + 1);

        // ... and inform the traversal again for this node
        trav_node_id.push_back(node);
        trav_depth.push_back(depth);
    }
}


// Structure to represent a query range
struct Query {
	int A, B;
};


// Fills lookup array 
// lookup[][] in bottom up manner.
void preprocess(vi& arr, int n, vector<vi>& lookup)
{
	// Initialize M for the 
	// intervals with length 1
	for (int i = 0; i < n; i++)
		lookup[i][0] = i;

	// Compute values from smaller 
	// to bigger intervals
	for (int j = 1; (1 << j) <= n; j++) 
	{
		// Compute minimum value for 
		// all intervals with size 2^j
		for (int i = 0; (i + (1 << j) - 1) < n; i++) 
		{
			if (arr[lookup[i][j - 1]]
				< arr[lookup[i + (1 << (j - 1))][j - 1]])
				lookup[i][j] = lookup[i][j - 1];
			else
				lookup[i][j]
					= lookup[i + (1 << (j - 1))][j - 1];
		}
	}
}

// Returns minimum of arr[L..R]
int minqueryidx(vi& arr, int L, int R, vector<vi>& lookup)
{
	int j = (int)log2(R - L + 1);
    int k = (1 << j); // 2^j
    return arr[lookup[L][j]] < arr[lookup[R - k + 1][j]] ?
           lookup[L][j] : lookup[R - k + 1][j];
}

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

    stringstream traces;

    // Successor graph
    vector<vi> succ (n);
    int e;
    for (int i = 1; i < n; i++) {
        cin >> e; e--;
        succ[e].push_back(i);
    }

    // Queries
    vector<Query> queries (q);
    int a,b;
    for (int i = 0; i < q; i++) {
        cin >> a >> b; a--; b--;
        queries[i].A = a;
        queries[i].B = b;
    }
    // traces << "-------- GRAPH --------" << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     traces << i << " -> ";
    //     for (auto& s : succ[i]) traces << s << ' ';
    //     traces << endl;
    // }
    // traces << "-----------------------" << endl << endl;

    
    // Traversal of the graph
    vi trav_node_id;
    vi trav_depth;
    dfs_traversal(0, succ, trav_node_id, trav_depth, 1);
    // traces << "-------- TRAVERSAL --------" << endl;
    // for (auto &&i : trav_node_id) traces << i << ' '; traces << endl;
    // for (auto &&i : trav_depth)   traces << i << ' '; traces << endl;
    // traces << "---------------------------" << endl << endl;
    
    

    // Preprocessing for min queries
    int N = trav_depth.size();
    vector<vi> lookup (N, vi((int)log2(N) + 1, -1));
    preprocess(trav_depth, N, lookup);
    // traces << "-------- LOOKUP TABLE --------" << endl;
    // for (auto &&v : lookup) {
    //     for (auto &&i : v) traces << i << ' ';
    //     traces << endl;
    // }
    // traces << "------------------------------" << endl << endl;

    


    // Last position of node_id in traversal
    vi node_id_trav_idx (n);
    for (int i = 0; i < N; i++)
    node_id_trav_idx[trav_node_id[i]] = i;

    // Queries treatment
    // traces << "-------- QUERIES --------" << endl;
    vi res;
    int r;
    for (auto &&q : queries)
    {
        int L = node_id_trav_idx[q.A];
        int R = node_id_trav_idx[q.B];
        if (L > R) swap(L,R);

        // traces << "lowest_common_ancestor(" << q.A << ", " << q.B << ")" <<
        //         " = minqueryidx(" << L << ", " << R << ") = ";

        r = trav_node_id[minqueryidx(trav_depth, L, R, lookup)];
        res.push_back(r);
        // traces << r << endl;
    }
    // traces << "-------------------------" << endl;

    // cout << traces.str();

    // Results
    for (auto &&r : res) cout << r + 1 << endl;
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED