#2025. Speike & Tom
Speike & Tom
Speike & Tom
题目描述
标题: Speike & Tom - Problem - QOJ.ac
#4901. Speike & Tom
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