试一试
2025-09-13 10:34:25
发布于：浙江
4阅读
0回复
0点赞
4120：【GESP2503八级】割裂
时间限制: 4000 ms 内存限制: 524288 KB
提交数: 148 通过数: 17
【题目描述】
小杨有一棵包含n
个节点的树，其中节点的编号从1
到n
。
小杨设置了a
个好点对{<u1,v1>,<u2,v2>,...,<ua,va>}
和1
个坏点对<bu,bv>
。一个节点能够被删除，当且仅当：
(1)删除该节点后对于所有的i
(1≤i≤a
)，好点对ui
和vi
仍然连通；
(2)删除该节点后坏点对 和 不连通。
如果点对中的任意一个节点被删除，其视为不连通。
小杨想知道，有多少个节点能够被删除。
【输入】
第一行包含两个正整数n,a
，含义如题面所示。
之后n−1
行，每行包含两个正整数xi,yi
，代表存在一条连接节点xi
和yi
的边。
之后a
行，每行包含两个正整数ui,vi
，代表一个好点对<ui,vi>
。
最后一行包含两个正整数bu,bv
，代表坏点对<bu,bv>
。
【输出】
输出一个正整数，代表能够删除的节点个数。
【输入样例】
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
【输出样例】
2
【提示】
数据范围
对于20%的数据，n≤10
,a=0
;
对于20%的数据，n≤100
,a≤100
;
对于60%的数据，n≤106
,a≤105
;
对于全部数据，保证1≤n≤106
，0≤a≤105
，ui≠vi
，bu≠bv
。
有帮助，赞一个