← 返回题单

题单练习 GESP八级真题-编程题

← 上一题下一题 →

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}$ 不连通｡ 如果点对中的任意一个节点被删除,其视为不连通｡ 小杨想知道,有多少个节点能够被删除｡

输入格式

第一行包含两个正整数 $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}$ 。

输出格式

输出一个正整数,代表能够删除的节点个数｡

输入输出样例

输入 #1

输出 #1

子任务编号分值na110%$10$$0$230%$\le100$$\le100$360%$\le10^6$$\le10^5$ 对于全部数据,保证有 $1 ≤n ≤10^{6},0 ≤a ≤10^{5} , u_{i} ≠v_{i} , b_{u} ≠b_{v}$。

C++ 编辑器

输入

输出