UOJ Logo Zijian Online Judge

ZOJ

统计

题目背景

这是忆哀的第多少次重生,已经无法统计。新生的花朵与离别的丧钟如同流水般流经她的眼帘。她脑中的仿佛不是过去的记忆,而也是无法改变的未来。

与其说这无穷轮回的折磨是一种「永生」,倒不如赐给她死亡。

但是这一次,她重新感受到了未知的那一丝"可能性"。跨过绝望……

在无数次重启中没有被复原的,不只是忆哀的记忆,还有那株由希望与血泪融汇,浇注生长出的来自「彼岸」的蔷薇。这便是能够与「祂」为之一战的武器。

题目描述

这株蔷薇一共生长出了 $n$ 朵花,它们之间连接形成一个树形结构。而已知有 $m$ 条路径,一条路径 $(a, b)$ 的含义是,将这条路径上的所有花朵放在一起,可以生成一种对抗神明的力量。但是一旦这种力量被生成出来,这朵花也被消耗,不能用于其他方案。也就是说,可以从树上选取一个点不相交的路径集合,每条路径得以生成一份力量。忆哀已经计算出了最多可以用这些花朵收集出多少份力量,但是……就差那么一点。

只要再多一份力量,就可以对抗神明了。

忆哀拿出剑,在手臂上划出一道伤口。她要选取一条路径,将这条路径上的花朵用鲜血染红,从而远古魔法将会得以生效,这些花朵也能够用于生成一份新的力量。

忆哀想知道,她一共有多少种不同的路径 $(x, y)$ 可以选择,也就是说将这条路径与原始的 $m$ 条路径一同考虑,能够选出来的最大的点不相交的路径集合,所包含的路径数比原来 $m$ 条路径中能选出来的路径数大。

向永恒开战,追寻我——

一如此刻,十指紧握。

将太阳射落,献给我——

请记得,我即神佛。

输入格式

第一行两个整数 $n, m$,表示蔷薇花的数量和原始的生成力量的方案数量。

接下来 $n - 1$ 行每行两个正整数 $u, v$,表示 $u$ 和 $v$ 两朵花直接相连。

接下来 $m$ 行每行两个正整数 $a, b$,表示 $a$ 到 $b$ 路径上的花朵整体可以生成一份力量。

输出格式

输出一行一个整数,表示忆哀可行的选择 $(a, b)$ 的方案数。

样例输入

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

样例输出

8

样例解释

原本可以选出 $2$ 条路径,例如:$(2, 3), (5, 8)$。

可以加入如下路径:

  • 加入 $(2,2)$,可以选择 $3$ 条路径:$(2, 2), (3, 4), (5, 8)$。
  • 加入 $(3, 3)$,可以选择 $3$ 条路径:$(3, 3), (2, 4), (5, 8)$。
  • 加入 $(4, 4)$,可以选择 $3$ 条路径:$(4, 4), (2, 3), (5, 8)$。
  • 加入 $(6, 6)$,可以选择 $3$ 条路径:$(6, 6), (2, 3), (5, 8)$。
  • 加入 $(7, 7)$,可以选择 $3$ 条路径:$(7, 7), (2, 3), (5, 6)$。
  • 加入 $(7, 8)$,可以选择 $3$ 条路径:$(7, 8), (2, 3), (5, 6)$。
  • 加入 $(8, 7)$,可以选择 $3$ 条路径:$(8, 7), (2, 3), (5, 6)$。
  • 加入 $(8, 8)$,可以选择 $3$ 条路径:$(8, 8), (2, 3), (5, 6)$。

因此总共有 $8$ 种加入路径的方案。

数据范围与约定

对于 $100\%$ 的数据,保证 $2\le n \le 3 \times 10^5, 0\le m \le 3\times 10^5, 1\le u, v, a, b\le n$。

测试点 $n$ $m$ 数据类型
$1,2$ $=10$ $\le10$ C2
$3,4$ $=20$ $\le20$
$5,6$ $=30$ $\le30$
$7,8$ $=10^2$ $\le10^2$
$9,10$ $=300$ $\le300$
$11$ $=500$ $\le500$
$12,13$ $=10^3$ $\le10^3$
$14,15$ $=3,000$ $\le3,000$
$16$ $=99,991$ $\le10^5$ A1
$17,18$ $=99,992$ A2
$19,20$ $=99,993$ B2
$21$ $=99,994$ C1
$22,23,24$ $=10^5$ C2
$25$ $=3\times 10^5$ $\le 3\times 10^5$

数据类型的含义:

A:保证 $v = u + 1$。

B:保证 $u = 1$。

C:在树的形态上无特殊约束。

1:保证 $a = b$。

2:给出的路径无特殊约束。

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

空间限制:$512\texttt{MB}$

下载

样例数据下载