Official Analysis

Alternative Solution

Time Complexity: $\mathcal O((n+m)\log n)$

For each path $(a, b)$, we can split it into two paths: $(a, lca(a, b)), (b, lca(a, b))$. We can find the lca with any method, but the easiest is with binary lifting. For each node, keep track of the number of paths that begin at that node and the number that end at that node.

If $k$ is the number of paths coming from a node's children, $s$ is the number of paths starting at the current node, and $e$ is the number of paths ending at the current node, then the answer for that node is $k + s - e / 2$. The $e / 2$ is because by splitting up the paths, we double count the lca for each path. The number of paths going to the node's parent is $k + s - e$. Thus, we can process all the paths at once using a single post-order traversal of the tree.

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

const int MAXN = 50001;
const int LOGN = 20;

int N, M;
vector<int> adj[MAXN];  // adj[u] = neighbors of u