#G1107. [GESP202503 八级] 割裂
[GESP202503 八级] 割裂
[GESP202503 八级] 割裂
时间限制:4.0 s 内存限制:512.0 MB
题目描述
小杨有一棵包含 个节点的树,其中节点的编号从 到 。
小杨设置了 个好点对 和 个坏点对 。一个节点能够被删除,当且仅当:
- 删除该节点后对于所有的 ,好点对 和 仍然连通;
- 删除该节点后坏点对 和 不连通。
如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,有多少个节点能够被删除。
输入格式
第一行包含两个正整数 ,含义如题面所示。
之后 行,每行包含两个正整数 ,代表存在一条连接节点 和 的边。
之后 行,每行包含两个正整数 ,代表一个好点对 。
最后一行包含两个正整数 ,代表坏点对 。
输出格式
输出一个正整数,代表能够删除的节点个数。
样例 #1
样例输入 #1
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
样例输出 #1
2
数据范围
| 子任务编号 | 分值 | ||
|---|---|---|---|
| 1 | 20% | 10 | 0 |
| 2 | |||
| 3 | 60% | ||
- 对于全部数据,保证有 ,,,。