← 返回题目列表

Codeforces · 1486/F

F. 路径对

中文机器翻译题面 查看原题

给你一棵由 $$$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)$$$ 相交于一个顶点。