Skip to content

1247: 割的计数

题目

题目描述

在一个 $N$ 个节点的无向图中,存在两类不同的边。

第一类边恰好有 $N - 1$ 条,将这 $N$ 个节点联通成为了一棵树的形态。

第二类边有 $M$ 条,任意生成。

如果我们在第一类边和第二类边中分别选择一条,然后把这两条边给切断,可以是的这 $N$ 个节点的无向图被切成两个不连通的部分,我们就认为这是一个割。

现在你需要统计,给定图中割的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$

之后 $N-1$ 行,每行包括两个整数 $a$ 和 $b$,表示 $a$ 和 $b$ 之间有一条第一类边

之后 $M$ 行以同样的格式给出第二类边

输出格式

输出一个整数表示答案

样例输入

text 4 1 1 2 2 3 1 4 3 4

样例输出

text 3

数据范围

对于 $20\%$ 的数据,$1\leq N, M\leq 100$;

对于 $60\%$ 的数据,$1\leq N, M\leq 1000$;

对于 $70\%$ 的数据,$1\leq N\leq 5000$;

对于 $100\%$ 的数据,$1\leq N\leq 10^5, 1\leq M \leq 2\times 10^5$。数据保证答案不超过 $2^{31}-1$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!