06601. GESP-8级-2025-03-割裂 · 林老师的题库

题目描述

小杨有一棵包含 $n$ 个节点的树，其中节点的编号从 $1$ 到 $n$ 。

小杨设置了 $a$ 个好点对 ${⟨ u_{1}, v_{1} ⟩, ⟨ u_{2}, v_{2} ⟩, \dots, ⟨ u_{a}, v_{a} ⟩}$ 和一个坏点对 $⟨ b_{u}, b_{v} ⟩$ 。一个节点能被删除，当且仅当：

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，还有多少个节点能被删除。

第一行包含两个非负整数 $n$ , $a$ ，含义如下题面所示。

接下来 $n - 1$ 行，每行包含两个正整数 $x_{i}, y_{i}$ ，代表存在一条连接节点 $x_{i}$ 和 $y_{i}$ 的边；

之后 $a$ 行，每行包含两个正整数 $u_{i}, v_{i}$ ，代表一个好点对 $⟨ u_{i}, v_{i} ⟩$ ；

最后一行包含两个正整数 $b_{u}, b_{v}$ ，代表坏点对 $⟨ b_{u}, b_{v} ⟩$ 。

输出一个非负整数，代表删除的节点个数。

输入

输出

子任务编号	分值	$n$	$a$
1	$20$	$= 10$	$= 0$
2	$20$	$\leq 100$	$\leq 100$
3	$60$	$\leq 1 0^{6}$	$\leq 1 0^{5}$

对于全部数据，保证有 $1 \leq n \leq 1 0^{6}$ , $0 \leq a \leq 1 0^{5}$ , $u_{i} \neq = v_{i}$ , $b_{u} \neq = b_{v}$ 。

来源：洛谷 P11967（CCF GESP 8 级上机题）