P16070 [ICPC 2023 NAC] A Tree and Two Edges

Given a connected simple graph (with at most one edge between any pair of nodes) with $ n $ nodes and $ n + 1 $ edges (that’s a tree with two extra edges), answer a list of queries: for two distinct nodes, how many simple paths are there between them? A simple path is a path that does not repeat nodes.

The first line of input contains two integers $ n $ ($ 4 \le n \le 5 \times 10^4 $) and $ q $ ($ 1 \le q \le 5 \times 10^4 $), where $ n $ is the number of nodes and $ q $ is the number of queries. The nodes are numbered from $ 1 $ to $ n $. Each of the next $ n + 1 $ lines contains two integers $ a $ and $ b $ ($ 1 \le a < b \le n $) indicating that there is an edge in the graph between nodes $ a $ and $ b $. All edges are distinct. Each of the next $ q $ lines contains two integers $ u $ and $ v $ ($ 1 \le u < v \le n $). This is a query for the number of simple paths between nodes $ u $ and $ v $.

Output $ q $ lines. On each line output a single integer, which is the number of simple paths between the query nodes. Output the answers to the queries in the order they appear in the input.