← 返回题目列表

Codeforces · 1336/F

F. 旅程

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

在远处的荒野中坐落着神圣之地,它可以被视为一棵树——由 $$$n$$$ 节点和 $$$n-1$$$ 边组成的连接无向图。节点编号从 $$$1$$$ 到 $$$n$$$。

有$$$m$$$旅客被它的繁荣和美丽所吸引。于是,他们踏上了这片土地的征程。第 $$$i$$$ 个旅行者将沿着从 $$$s_i$$$ 到 $$$t_i$$$ 的最短路径行进。这样做时,它们将遍历从 $$$s_i$$$ 到 $$$t_i$$$ 的最短路径中的所有边,这在树中是唯一的。

在旅途中,旅行者会结识其他人。有些甚至可能成为朋友。具体来说,当且仅当存在至少 $$$k$$$ 条边,第 $$$i$$$ 个旅行者和第 $$$j$$$ 个旅行者都会成为朋友。

你的任务是找出满足以下条件的旅行者 $$$(i, j)$$$ 对的数量:

- $$$1 \leq i < j \leq m$$$。
- 第 $$$i$$$ 个旅行者和第 $$$j$$$ 个旅行者将成为朋友。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n, m \le 1.5 \cdot 10^5$$$, $$$1\le k\le n$$$)。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),表示 $$$u$$$ 和 $$$v$$$ 之间有一条边。

接下来的$$$m$$$行中的第$$$i$$$行包含两个整数$$$s_i$$$和$$$t_i$$$ ($$$1\le s_i,t_i\le n$$$, $$$s_i \neq t_i$$$),分别表示第$$$i$$$的起点和终点旅行者。

保证给定的边形成一棵树。

输出

唯一的一行包含一个整数 - 满足给定条件的旅行者对的数量。

示例

输入 #1

8 4 1
1 7
1 2
2 5
4 6
6 3
6 2
6 8
7 8
3 8
2 6
4 1

输出 #1

4

输入 #2

10 4 2
3 10
9 3
4 9
4 6
8 2
1 7
2 1
4 5
6 7
7 1
8 7
9 2
10 3

输出 #2

1

输入 #3

13 8 3
7 6
9 11
5 6
11 3
9 7
2 12
4 3
1 2
5 8
6 13
5 10
3 1
10 4
10 11
8 11
4 9
2 5
3 5
7 3
8 10

输出 #3

14

注意

在第一个示例中,有 $$$4$$$ 对满足给定的要求:$$$(1,2)$$$、$$$(1,3)$$$、$$$(1,4)$$$、$$$(3,4)$$$。

- $$$1$$$-st 旅行者和 $$$2$$$-nd 旅行者都穿过边缘 $$$6-8$$$。
- $$$1$$$-st 旅行者和 $$$3$$$-rd 旅行者都穿过边缘 $$$2-6$$$。
- 第$$$1$$$个旅行者和第$$$4$$$个旅行者都穿过边缘$$$1-2$$$和$$$2-6$$$。
- 第 $$$3$$$ 个旅行者和第 $$$4$$$ 个旅行者都穿过边缘 $$$2-6$$$。