给你一棵由 $$$n$$$ 个顶点和 $$$m$$$ 个简单顶点路径组成的树。您的任务是找出有多少对这些路径恰好在一个顶点处相交。更正式地说,你必须找到 $$$(i, j)$$$ $$$(1 \leq i < j \leq m)$$$ 的对数,使得 $$$path_i$$$ 和 $$$path_j$$$ 恰好有一个公共顶点。
输入
第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 3 \cdot 10^5)$$$。
接下来的 $$$n - 1$$$ 行描述了树。每行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \leq u, v \leq n)$$$ 描述顶点 $$$u$$$ 和 $$$v$$$ 之间的边。
下一行包含一个整数 $$$m$$$ $$$(1 \leq m \leq 3 \cdot 10^5)$$$。
接下来的 $$$m$$$ 行描述路径。每行通过两个端点 $$$u$$$ 和 $$$v$$$ $$$(1 \leq u, v \leq n)$$$ 描述一条路径。给定路径是从$$$u$$$到$$$v$$$的最短路径上的所有顶点(包括$$$u$$$和$$$v$$$)。
输出
输出一个整数——恰好在一个顶点相交的路径对的数量。
示例
输入 #1
5 1 2 1 3 1 4 3 5 4 2 3 2 4 3 4 3 5
输出 #1
2
输入 #2
1 3 1 1 1 1 1 1
输出 #2
3
输入 #3
5 1 2 1 3 1 4 3 5 6 2 3 2 4 3 4 3 5 1 1 1 2
输出 #3
7
注意
第一个示例中的树和路径如下所示。对 $$$(1,4)$$$ 和 $$$(3,4)$$$ 相交于一个顶点。
在第二个示例中,所有三个路径都包含相同的单个顶点,因此所有对 $$$(1, 2)$$$、$$$(1, 3)$$$ 和 $$$(2, 3)$$$ 都在一个顶点处相交。
第三个示例与第一个示例相同,但有两个附加路径。对 $$$(1,4)$$$、$$$(1,5)$$$、$$$(2,5)$$$、$$$(3,4)$$$、$$$(3,5)$$$、$$$(3,6)$$$ 和 $$$(5,6)$$$ 相交于一个顶点。