#3046. 「ZJOI2019」语言

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

九条可怜是一个喜欢规律的女孩子。按照规律,第二题应该是一道和数据结构有关的题。

在一个遥远的国度,有 n 个城市。城市之间有 n − 1 条双向道路,这些道路保证了任何两个城市之间都能直接或者间接地到达。

在上古时代,这 n 个城市之间处于战争状态。在高度闭塞的环境中,每个城市都发展出了自己的语言。而在王国统一之后,语言不通给王国的发展带来了极大的阻碍。为了改善这种情况,国王下令设计了 m 种通用语,并进行了 m 次语言统一工作。在第 i 次统一工作中,一名大臣从城市 s_i 出发,沿着最短的路径走到了 t_i ,教会了沿途所有城市(包括 s_i, t_i )使用第 i 个通用语。

一旦有了共通的语言,那么城市之间就可以开展贸易活动了。两个城市 u_i, v_i 之间可以开展贸易活动当且仅当存在一种通用语 L 满足 u_i v_i 最短路上的所有城市(包括 u_i, v_i ),都会使用 L

为了衡量语言统一工作的效果,国王想让你计算有多少对城市 (u, v)\ (u < v) ,他们之间可以开展贸易活动。

输入格式

第一行输入两个正整数 n, m ,表示城市数和通用语的数量。
接下来 n − 1 行,每行两个整数 x_i, y_i\ (1 \le x_i, y_i \le n) ,表示了一条连接城市 x_i, y_i 的道路。
接下来 m 行,每行两个整数 s_i, t_i\ (1 \le s_i, t_i \le n, s_i\neq t_i) ,表示一次语言普及工作。

输出格式

输出一行一个整数,表示可以开展贸易活动的城市对数量。

样例

样例输入 1

5 3
1 2
1 3
3 4
3 5
3 4
1 4
2 5

样例输出 1

8

样例说明 1

可以开展贸易活动的城市对为 (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)

样例 2

见附加文件 language1.in/ans

数据范围与提示

测试点 n m 其他约定
1,2 \le 300 \le 300
3,4 \le 5\times 10^3 \le 5\times 10^3
5,6 \le 10^5 \le 10^5 y_i=x_i+1
7\sim 10

对于 100\% 的数据,有 1 \le x_i, y_i, s_i, t_i \le n, m \ge 1, x_i\neq y_i