Distances at Scale

Difficulty: 1900 6000 ms 128 MB

trees binary-lifting

Answer Q distance queries on a tree: the number of edges between A and B.

Input: the first line has N and Q; the next N−1 lines have the edges; the next Q lines have the query pairs.

Output: one line per query.

Constraints:

• 2 ≤ N, Q ≤ 2×10⁵ (tests smaller)

Sample Tests

5 2
1 2
1 3
3 4
3 5
4 5
2 4

2
3

2 1
1 2
1 2

1

Read the Editorial