题目描述

Dark 是一张无向图，图中有 $N$ 个节点和两类边：

• 主要边：有 $N-1$ 条，并且任意两个节点之间都存在一条只由主要边构成的路径（即主要边构成一棵树）；
• 附加边：有 $M$ 条。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的，而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

---

输入格式

第一行包含两个整数 $N$ 和 $M$；

之后 $N–1$ 行，每行包括两个整数 $A$ 和 $B$，表示 $A$ 和 $B$ 之间有一条主要边；

之后 $M$ 行以同样的格式给出附加边。

---

输出格式

输出一个整数表示答案。

---

样例

输入样例 1

4 1 
1 2 
2 3 
1 4 
3 4

输出样例 1

3

样例解释

主要边构成一棵树：

1--2
|   |
4   3

附加边是 $(3, 4)$。

枚举切断每条主要边后的情况：

1. 切断边 $(1,2)$：

   • 此时图被分成两部分：$\{1,4\}$ 和 $\{2,3\}$。
   • 再切掉附加边 $(3,4)$ 可以使图不连通吗？不可以，因为 $(3,4)$ 连接的是不同部分，切掉它不会使任何一个部分内部断开。
   • 所以没有合法方案。

2. 切断边 $(2,3)$：

   • 图被分成 $\{1,2,4\}$ 和 $\{3\}$。
   • 需要再切断一条附加边使图不连通。唯一附加边是 $(3,4)$，它连接了 $\{3\}$ 和 $\{1,2,4\}$，切掉它可以使 $\{3\}$ 独立出来，方案有效。
   • 1 种方案。

3. 切断边 $(1,4)$：

   • 图被分成 $\{1,2,3\}$ 和 $\{4\}$。
   • 切掉附加边 $(3,4)$ 连接 $\{1,2,3\}$ 和 $\{4\}$，切掉它可以使 $\{4\}$ 独立，方案有效。
   • 1 种方案。

另外，切断主要边 $(1,2)$ 后图已经断开，但仍需切一条附加边，而附加边 $(3,4)$ 连接两个部分，切掉不会使某个部分内部断开，所以不算合法方案。

总共方案数 = 1 + 1 + 1 = 3？
等一下，重新分析：
实际上树的结构是：

  1
 / \
2   4
 \
  3

主要边：$(1,2),\ (2,3),\ (1,4)$
附加边：$(3,4)$

枚举每条主要边：

1. 切断 $(1,2)$：分成 $\{1,4\}$ 和 $\{2,3\}$，附加边 $(3,4)$ 连接两个部分，切掉它不会让任何部分内部不连通，所以不行。
2. 切断 $(2,3)$：分成 $\{1,2,4\}$ 和 $\{3\}$，切掉 $(3,4)$ 可以让 $\{3\}$ 孤立，可行。
3. 切断 $(1,4)$：分成 $\{1,2,3\}$ 和 $\{4\}$，切掉 $(3,4)$ 可以让 $\{4\}$ 孤立，可行。

所以答案是 $2$？
但样例输出是 $3$。

仔细看题：“就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。”

意思是：即使第一步切断主要边后图已经分成两个连通块，也必须再切断一条附加边（即使那条附加边是连接两个块的，切断后不会改变连通块数，但规则要求必须切一条附加边）。

因此：

• 切断 $(1,2)$：图已经断开，再切附加边 $(3,4)$ 即可，即使它连接两个块，也算符合规则 → 1 种方案。
• 切断 $(2,3)$：图分成 $\{1,2,4\}$ 和 $\{3\}$，必须切附加边 $(3,4)$ 连接两个块，切掉后 $\{3\}$ 独立 → 1 种方案。
• 切断 $(1,4)$：图分成 $\{1,2,3\}$ 和 $\{4\}$，切掉附加边 $(3,4)$ 连接两个块，切掉后 $\{4\}$ 独立 → 1 种方案。

总共 $3$ 种方案。

---

数据范围

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• 答案保证在 $2^{31}-1$ 以内。

时间限制：1000 ms
内存限制：524288 KB

---

提示

这是一个树上差分（边差分）与最近公共祖先（LCA）结合的问题。

考虑每条附加边 $(u,v)$，它和树上的路径 $u \to v$ 形成了一个环。如果切断了这个环上的某条主要边，那么必须再切断这条附加边，才能使图不连通。

定义 $cnt[e]$ 表示覆盖主要边 $e$ 的附加边的数量。对于每条附加边 $(u,v)$，将 $u$ 到 $v$ 路径上的所有主要边的 $cnt$ 加 $1$（可以使用树上边差分实现）。

然后枚举每条主要边 $e$：

• 如果 $cnt[e] = 0$，那么切断这条主要边后图已经断开，此时可以任意选择一条附加边切断，方案数为 $M$。
• 如果 $cnt[e] = 1$，那么切断这条主要边后，必须切断那条覆盖它的附加边，方案数为 $1$。
• 如果 $cnt[e] \ge 2$，那么切断这条主要边后，至少需要切断两条附加边才能断开图，但题目只允许再切一条附加边，所以方案数为 $0$。

总方案数即为上述三种情况的累加。

实现步骤：

1. 以任意节点为根，用 DFS 预处理深度和倍增数组用于求 LCA。
2. 读入附加边，对于每条附加边 $(u,v)$，利用 LCA 计算路径，并用差分数组 $diff[u]++,\ diff[v]++,\ diff[lca(u,v)]-=2$。
3. 第二次 DFS 计算每个节点的子树差分和，这个值就是连接该节点与其父节点的那条主要边的 $cnt$ 值。
4. 统计答案。

时间复杂度：$O((N+M)\log N)$。