P16070 [ICPC 2023 NAC] A Tree and Two Edges

给定一个连通简单图（任意两个节点之间至多有一条边），该图有 $ n $ 个节点和 $ n + 1 $ 条边（即一棵树加上两条额外的边）。请回答一系列询问：对于两个不同的节点，它们之间有多少条简单路径？简单路径是指不重复节点的路径。

输入的第一行包含两个整数 $ n $（$ 4 \le n \le 5 \times 10^4 $）和 $ q $（$ 1 \le q \le 5 \times 10^4 $），其中 $ n $ 是节点数，$ q $ 是询问数。节点编号为 $ 1 $ 到 $ n $。 接下来的 $ n + 1 $ 行，每行包含两个整数 $ a $ 和 $ b $（$ 1 \le a < b \le n $），表示节点 $ a $ 与 $ b $ 之间有一条边。所有边互不相同。 接下来的 $ q $ 行，每行包含两个整数 $ u $ 和 $ v $（$ 1 \le u < v \le n $），表示询问节点 $ u $ 与 $ v $ 之间的简单路径数量。

输出 $ q $ 行，每行一个整数，表示询问节点之间的简单路径数量。按照输入中出现的顺序输出每个询问的答案。

翻译由 DeepSeek V3.2 完成