Basic idea is to answer the queries offline using rerooting technique.

Similarly to the official editorial, we’ll use binary lifting (k-th ancestor and lowest common ancestor) to find the “mid-edge” of the path between \(L_i\) and \(R_i\), but instead of trying to find the formula for the answer right there, we store two queries of the form \((u, i, v, d)\), meaning “when the root is \(u\), add to \(ans_i\) the sum of distances from every node to \(u\), except for the subtree of node \(v\). (\(d\) is the distance between \(u\) and \(v\), which is more conveniently precalculated, as you can’t update depths while rerooting)”. Note that the case \(L_i = R_i\) has to be handled specially, with only one query but no subtree exception.

We then do an Euler traversal of the tree; for each edge we traverse over we “reroot” to the new vertex, and if it’s the first time we visit that vertex, we answer all the enqueued queries where \(u = \) that vertex. We need only keep track of two values per node: \(sz_v\), the number of nodes in the subtree of \(v\), and \(sum_v\), the sum of distances from each node in the subtree of \(v\) to node \(v\). The contribution of each \((u, i, v, d)\) query is then \(sum_u - sum_v - d \cdot sz_v\) .

Code Example (Rust)