CF1336F Journey

在遥远的荒野之外，有一片神圣之地，可以看作是一棵树——一个包含 $n$ 个节点和 $n-1$ 条边的连通无向图。节点编号为 $1$ 到 $n$。 有 $m$ 位旅行者被这里的繁荣与美丽所吸引，踏上了这片土地的旅程。第 $i$ 位旅行者将沿着从 $s_i$ 到 $t_i$ 的最短路径旅行。在旅途中，他们会经过从 $s_i$ 到 $t_i$ 的所有最短路径上的边，而在树中这条路径是唯一的。 在旅行过程中，旅行者们会彼此认识，有些甚至会成为朋友。具体来说，只有当第 $i$ 位旅行者和第 $j$ 位旅行者都经过至少 $k$ 条相同的边时，他们才会成为朋友。 你的任务是计算满足以下条件的旅行者对数 $(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$ 位旅行者的起点和终点。 保证所给的边构成一棵树。

输出一行一个整数，表示满足条件的旅行者对数。

 在第一个样例中，有 $4$ 对满足条件的旅行者对：$(1,2)$、$(1,3)$、$(1,4)$、$(3,4)$。 - 第 $1$ 位和第 $2$ 位旅行者都经过了边 $6-8$。 - 第 $1$ 位和第 $3$ 位旅行者都经过了边 $2-6$。 - 第 $1$ 位和第 $4$ 位旅行者都经过了边 $1-2$ 和 $2-6$。 - 第 $3$ 位和第 $4$ 位旅行者都经过了边 $2-6$。 由 ChatGPT 4.1 翻译