#PQJ468x2580. QOJ 468_2580
QOJ 468_2580
2 语言 2.1 题目ᦣ䗄 九条可怜是一个喜欢规律的女孩子。按照规律,第二题应该是一道和数据结构有关的题。 在一个遥远的国度,有n 个城市。城市之间有n −1 条双向道路,这些道路保证了任何两 个城市之间都能直接或者间接地到达。 在上古时代,这n 个城市之间处于战争状态。在高度闭塞的环境中,每个城市都发展出了 自己的语言。而在王国统一之后,语言不通给王国的发展带来了极大的阻碍。为了改善这种情 况,国王下令设计了m 种通用语,并进行了m 次语言统一工作。在第i 次统一工作中,一名 大臣从城市si 出发,沿着最短的路径走到了ti,教会了沿途所有城市(包括si, ti)使用第i 个 通用语。 一旦有了共通的语言,那么城市之间就可以开展贸易活动了。两个城市ui, vi 之间可以开 展贸易活动当且仅当存在一种通用语L 满足ui 到vi 最短路上的所有城市(包括ui, vi),都会 使用L。 为了衡量语言统一工作的效果,国王想让你计算有多少对城市(u, v)(u < v),他们之间可 以开展贸易活动。 2.2 输入格式 第一行输入两个正整数n, m,表示城市数和通用语的数量。 接下来n −1 行,每行两个整数xi, yi(1 ≤xi, yi ≤n),表示了一条连接城市xi, yi 的道路。 接下来m 行,每行两个整数si, ti(1 ≤si, ti ≤n, si̸ = ti),表示一次语言普及工作。 2.3 输出格式 输出一行一个整数,表示可以开展贸易活动的城市对数量。 2.4 样例输入 5 3 1 2 1 3 3 4 3 5 3 4 1 4 2 5 4
2.5 样例输出 8 2.6 样例㾷䞞 可以开展贸易活动的城市对为(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)。 2.7 数据㣗ೈϢ约定 测试点 n m 其他约定 1 ≤300 ≤300 无 2 3 ≤5000 ≤5000 4 5 ≤105 ≤105 yi = xi + 1 6 7 无 8 9 10 对于100% 的数据,有1 ≤si, yi, si, ti ≤n, m ≥1, si̸ = ti, xi̸ = yi。 5