[GESP202503 八级] 割裂

普及+/提高 GESP 八级 真题

题目描述

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

小杨设置了 $ a $ 个好点对 ${\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 $。

输出格式

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

数据范围

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

对于全部数据,保证有 $ 1 \leq n \leq 10^6 $, $ 0 \leq a \leq 10^5 $, $ u_i \neq v_i $, $ b_u \neq b_v $。

样例输入 1

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6

样例输出 1

2
时间限制: 1000ms
内存限制: 256MB
通过率: 0.0%
提交数: 0

设置

导航栏小工具

时钟
显示实时时钟(默认组件)
📝
代码粘贴板
快速创建和分享代码片段