960. LCA + Distance Queries on a Tree

Given a tree with n nodes labeled 0..n-1 rooted at node 0, described by an undirected edge list, answer a batch of queries: for each pair [u, v], return the distance between them (the number of edges on the unique path). Use LCA via binary lifting: distance = depth[u] + depth[v] - 2*depth[lca]. Return the answers as an array in order. The input is JSON {n, edges, queries}.

Input: JSON {n, edges, queries}.

Output: Array — the distance for each query.

Examples

Input: {"n":7,"edges":[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],"queries":[[3,4],[3,5],[6,6]]}
Output: [2,4,0]
Explanation: Edge distances between pairs.

Input: {"n":1,"edges":[],"queries":[[0,0]]}
Output: [0]
Explanation: Same node.

Input: {"n":3,"edges":[[0,1],[0,2]],"queries":[[1,2]]}
Output: [2]
Explanation: Two edges apart.

Constraints

• 1<=n<=10^5
• edges form a tree rooted at 0
• 1<=queries<=10^5

Asked by