[GESP202503 八级] 割裂
说明
小杨有一棵包含 $ n $ 个节点的树，其中节点的编号从 1 到 $ n $。
小杨设置了一个好点对 $\{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\}$ 和一个坏点对 $\langle b_u, b_v \rangle$。一个节点能被删除，当且仅当：
- 删除该节点后对于所有的 $ 1 \leq i \leq a $，好点对 $ u_i $ 和 $ v_i $ 仍然连通；
- 删除该节点后坏点对 $ b_u $ 和 $ b_v $ 不连通。
如果点对中的任意一个节点被删除，其视为不连通。
小杨想知道，还有多少个节点能被删除。
输入格式
第一行包含两个非负整数 $ n $, $ a $，含义如下题面所示。
接下来 $n - 1$ 行，每行包含两个正整数 $ x_i, y_i $，代表存在一条连接节点 $ x_i $ 和 $ y_i $ 的边；
之后 $ a $ 行，每行包含两个正整数 $ u_i, v_i $，代表一个好点对 $ \langle u_i, v_i \rangle $；
最后一行包含两个正整数 $ b_u, b_v $，代表坏点对 $ \langle b_u, b_v \rangle $。
输出格式
输出一个非负整数，代表删除的节点个数。样例
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 62提示
对于全部数据，保证有 $ 1 \leq n \leq 10^6 $, $ 0 \leq a \leq 10^5 $, $ u_i \neq v_i $, $ b_u \neq b_v $
|
子任务编号 |
分值 |
$ n $ |
$ a $ |
|
$1$ |
$20$ |
$=10$ |
$=0$ |
|
$2$ |
$20$ |
$ \leq 100 $ |
$ \leq 100 $ |
|
$3$ |
$60$ |
$ \leq 10^6 $ |
$ \leq 10^5 $ |