A5187. [GESP202503 八级] 割裂
编程题
普及+/提高
知识点
题目描述
小杨有一棵包含 $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}$。