Explanation

This problem asks us to find the lowest common ancestor (LCA) of two nodes in a tree. While this can be solved with binary lifting, we'll use Heavy-Light Decomposition (HLD) to practice the technique.

HLD Preprocessing:

• Compute subtree sizes to identify heavy children
• Decompose the tree into heavy paths
• Assign each node to a heavy path chain and store the top node

The key insight is that we can efficiently jump between heavy path chains when traversing from node $a$ to node $b$. To find the LCA of two nodes:

1. Repeatedly move the node with the deeper heavy path chain to its parent chain
2. When both nodes are on the same heavy path chain, the node with smaller depth is the LCA

Any path passes through at most $\log N$ light edges and thus needs to jump through a max of $\log N$ heavy paths.

Implementation

Time Complexity: $\mathcal{O}(N + Q \log N)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 2e5 + 5;

int n, q;
vector<int> adj[N];