java - 在图中查找顶点对的数量，使得它们之间的路径只有一个与不同给定路径共有的顶点

Question

给定一棵具有 N 个顶点和 N-1 个无向边的树。1<=N<=250000 需要执行某些查询。1<=Q<=10^5 在每个查询中，我们将获得两个顶点，例如 a 和 b。我们必须告诉顶点对的数量，使得它们之间的路径恰好包含一个顶点，该顶点与顶点 a 和 b 之间的路径中存在的顶点相同。例如：N=6.所以N-1条边。--> 1 2, 1 3, 1 4, 2 5, 2 6. （意思是1接2,3,4，2接1,5 ,6)

让我们的查询是 a 和 b--> 4 5。

答案将是 6。（表示在给定条件的图中存在 6 对顶点）这 6 对顶点是：1 1、2 2、4 4、5 5、1 3、2 6。

我一直在思考这个问题 2 天，但我无法得到任何完美的逻辑。我首先认为我们可以使用 LCA（最低共同祖先）找到，但后来我找不到如何找到。

请帮助我获取一些逻辑，以便我可以有效地解决它。

标签： javac++data-structuresgraphtree