QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 4901. Speike & Tom

Statistics

时间限制:$\mathrm{2s}$

空间限制:$\mathrm{512Mb}$。

题目描述

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

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

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

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

现在 Tom 想要知道,对于所有的 $n\times (n−1)$ 组可能的 $(a,b)\ (a\neq 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\leq n,m\leq 10^5$,$1\leq x,y\leq n$,对于最后 $m$ 行,保证 $x \ne y$ 且所有无序对 $(x,y)$ 不同,但不保证 $(x,y)$ 这条边不在树中。

Subtask 1($10$ pts):$n,m \leq 20$。

Subtask 2($15$ pts):$n,m \leq 300$。

Subtask 3($15$ pts):$n,m \leq 2000$。

Subtask 4($20$ pts):$n,m \leq 40000$。

Subtask 5($10$ pts):$m = 1$。

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