UOJ Logo Universal Online Judge

UOJ

#470. 【ZJOI2019】语言

附件下载 统计

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

在一个遥远的国度,有 $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 \leq x_i,y_i \leq n)$,表示了一条连接城市 $x_i,y_i$ 的道路。

接下来 $m$ 行,每行两个整数 $s_i,t_i(1 \leq s_i,t_i \leq n,s_i \neq t_i)$,表示一次语言普及工作。

输出格式

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

样例一

input

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

output

8

explanation

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

样例二

见样例数据下载

限制与约定

对于 $100\%$ 的数据,有 $1 \leq s_i,y_i,s_i,t_i \leq n, m \geq 1, s_i \neq t_i, x_i \neq y_i$。

测试点 $n$ $m$ 其他限制
1 $\leq 300$ $\leq 300$
2
3 $\leq 5000$ $\leq 5000$
4
5 $\leq 10^5$ $\leq 10^5$ $y_i=x_i+1$
6
7
8
9
10

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载