A5187 | [GESP202503 八级] 割裂
来源2025
时间限制4s
内存限制512MB
通过 / 提交0/0
题目描述
小杨有一棵包含 $n$ 个节点的树,其中节点的编号从 $1$ , $n$ 。
小杨设置了 $a$ 个好点对 $\{ < u_1,v_1 > , < u_2 , v_2 > ,\dots , < u_a,v_a > \}$ 和一对坏节点 $< b_u,b_v >$ . 一个节点能够被删除,当 且仅当:
- 删除该节点后对于所有的 $i(1 ≤i ≤a)$ ,好点对 $u_{i}$ 和 $v_{i}$ 仍然连通;
- 删除该节点后坏点对 $b_{u}$ 和 $b_{v}$ 不连通｡
如果点对中的任意一个节点被删除,其视为不连通｡
小杨想知道,有多少个节点能够被删除｡
小杨设置了 $a$ 个好点对 $\{ < u_1,v_1 > , < u_2 , v_2 > ,\dots , < u_a,v_a > \}$ 和一对坏节点 $< b_u,b_v >$ . 一个节点能够被删除,当 且仅当:
- 删除该节点后对于所有的 $i(1 ≤i ≤a)$ ,好点对 $u_{i}$ 和 $v_{i}$ 仍然连通;
- 删除该节点后坏点对 $b_{u}$ 和 $b_{v}$ 不连通｡
如果点对中的任意一个节点被删除,其视为不连通｡
小杨想知道,有多少个节点能够被删除｡
输入格式
第一行包含两个正整数 $n , a$ ,含义如题面所示｡
之后 $n-1$ 行,每行包含两个正整数 $x_{i}, y_{i}$ ,代表存在一条连接节点 $x_{i}$ 和 $y_{i}$ 的边｡
之后 $a$ 行,每行包含两个正整数 $u_{1}$ , $v_{i}$ ,代表一个好点对 $<u_{i} , v_{i}>$ 。
最后一行包含两个正整数 $b_{u} , b_{v}$ ,代表坏点对 $<b_{u} , b_{v}>$ 。
之后 $n-1$ 行,每行包含两个正整数 $x_{i}, y_{i}$ ,代表存在一条连接节点 $x_{i}$ 和 $y_{i}$ 的边｡
之后 $a$ 行,每行包含两个正整数 $u_{1}$ , $v_{i}$ ,代表一个好点对 $<u_{i} , v_{i}>$ 。
最后一行包含两个正整数 $b_{u} , b_{v}$ ,代表坏点对 $<b_{u} , b_{v}>$ 。
输出格式
输出一个正整数,代表能够删除的节点个数｡
输入输出样例
输入 #1
6 2 1 3 1 5 3 6 3 2 5 4 5 4 5 3 2 6
输出 #1
2
| 子任务编号 | 分值 |n|a|
| --- | --- |---|---|
| 1 | 10%|$10$|$0$|
| 2 | 30% |$\le100$|$\le100$|
| 3 | 60% |$\le10^6$|$\le10^5$|
对于全部数据,保证有 $1 ≤n ≤10^{6},0 ≤a ≤10^{5} , u_{i} ≠v_{i} , b_{u} ≠b_{v}$。
| --- | --- |---|---|
| 1 | 10%|$10$|$0$|
| 2 | 30% |$\le100$|$\le100$|
| 3 | 60% |$\le10^6$|$\le10^5$|
对于全部数据,保证有 $1 ≤n ≤10^{6},0 ≤a ≤10^{5} , u_{i} ≠v_{i} , b_{u} ≠b_{v}$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？