P5327 [ZJOI2019]语言

    • 167通过
    • 411提交
  • 题目提供者 Chhokmah
  • 评测方式 云端评测
  • 标签 各省省选 2019 浙江 O2优化
  • 难度 NOI/NOI+/CTSC
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    在一个遥远的国度,有 $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, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)$。

    数据范围

    测试点 $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$ $\le 10^5$ $\le 10^5$

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。