#G1107. [GESP202503 八级] 割裂

[GESP202503 八级] 割裂

[GESP202503 八级] 割裂

时间限制:4.0 s 内存限制:512.0 MB

题目描述

小杨有一棵包含 nn 个节点的树,其中节点的编号从 11 到 nn。

小杨设置了 aa 个好点对 <u1,v1>,<u2,v2>,…,<ua,va><u_1,v_1>,<u_2,v_2>,\dots,<u_a,v_a> 和 11 个坏点对 <bu,bv><b_u,b_v>。一个节点能够被删除,当且仅当:

  • 删除该节点后对于所有的 i (1≤i≤a)i\ (1\le i\le a),好点对 uiu_i 和 viv_i 仍然连通;
  • 删除该节点后坏点对 bub_u 和 bvb_v 不连通。

如果点对中的任意一个节点被删除,其视为不连通。

小杨想知道,有多少个节点能够被删除。

输入格式

第一行包含两个正整数 n,an,a,含义如题面所示。

之后 n−1n-1 行,每行包含两个正整数 xi,yix_i,y_i,代表存在一条连接节点 xix_i 和 yiy_i 的边。

之后 aa 行,每行包含两个正整数 ui,viu_i,v_i,代表一个好点对 <ui,vi><u_i,v_i>。

最后一行包含两个正整数 bu,bvb_u,b_v,代表坏点对 <bu,bv><b_u,b_v>。

输出格式

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

样例 #1

样例输入 #1

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6

样例输出 #1

2

数据范围

子任务编号 分值 nn aa
1 20% 10 0
2 ≤100\le 100
3 60% ≤106\le 10^6 ≤105\le 10^5
  • 对于全部数据,保证有 1≤n≤1061\le n\le 10^6,0≤a≤1050\le a\le 10^5,ui≠viu_i\ne v_i,bu≠bvb_u\ne b_v。