#2025. Speike & Tom

    ID: 2025 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest757来源:qoj.ac数据:公开样例最短路

Speike & Tom

Speike & Tom

题目描述

标题: Speike & Tom - Problem - QOJ.ac

#4901. Speike & Tom

Statistics

The problem was used in the following contests:

时间限制:2s

空间限制:512Mb。

题目描述

一次 Tom 用鞭炮炸 Jerry 的老鼠洞时,不小心炸到了 Speike 的狗窝。

后院的道路构成了一棵 n 个点的无向树,Speike 与 Tom 之间的追逐以如下方式展开:

  • Tom 和 Speike 一开始分别在 a,b 两个点;
  • Tom 和 Speike 轮流行动,Tom 先行;
  • 每次行动者可以选择不动,或是沿着一条边走到另一个端点;
  • 如果一次行动后到达了 Speike 和 Tom 处于同一位置则 Speike 胜。

以 Tom 的智商足够知道这个游戏他是必败的,所以他趁 Speike 没反应过来之前建立了 m 条额外边,这些额外边只能被 Tom 经过,而不能被 Speike 经过。

现在 Tom 想要知道,对于所有的 n×(n−1) 组可能的 (a,b) (a≠b),有多少组追逐中 Tom 有策略使得 Speike 永远无法获胜。

输入格式

第一行:两个整数 n,m。

接下来 n−1 行:每行两个整数 x,y,描述一条树边。

接下来 m 行:每行两个整数 x,y,描述一条额外边。

输出格式

输出一行:一个整数表示答案。

样例 1 输入输出

input

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

output

18

样例 1 解释

样例中的图如下图所示,黑色为树边,红色为额外边,共有 18 个点对使得 Speike 无法获胜,其中 Tom 和 Speike 的初始位置分别是 (1,2),(1,3),(1,4),(1,5),(2,1),(2,3),(2,4),(2,5),(3,1)(3,2),(3,4),(3,5),(4,1),(4,2),(4,3),(4,5),(5,1),(5,2)。

样例 2 输入输出

input

9 2
1 2
2 3
3 4
2 5
5 6
6 7
7 8
1 9
1 5
5 8

output

48

限制与约束

本题采用捆绑测试。

对于 100% 的数据:1≤n,m≤105,1≤x,y≤n,对于最后 m 行,保证 x≠y 且所有无序对 (x,y) 不同,但不保证 (x,y) 这条边不在树中。

Subtask 1(10 pts):n,m≤20。

Subtask 2(15 pts):n,m≤300。

Subtask 3(15 pts):n,m≤2000。

Subtask 4(20 pts):n,m≤40000。

Subtask 5(10 pts):m=1。

Subtask 6(30 pts):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

9 2
1 2
2 3
3 4
2 5
5 6
6 7
7 8
1 9
1 5
5 8
48