描述
Dark 是一张无向图，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 N–1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 M 条附加边。
你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。
现在你想要知道，一共有多少种方案可以击败 Dark。注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。
输入
第一行包含两个整数 N 和 M；
之后 N–1行，每行包括两个整数 A 和 B，表示 A 和 B 之间有一条主要边；
之后 M 行以同样的格式给出附加边。
对于 20% 的数据，1≤N,M≤100；
对于 100% 的数据，1≤N≤105,1≤M≤2×105 。数据保证答案不超过 231−1。
输出
输出一个整数表示答案。
样例输入
4 1
1 2
2 3
1 4
3 4
样例输出
3
这道题目的主要目标是找出有多少种方式可以将图 "Dark" 斩为两部分。这个过程包括两步：首先，你需要选择一条主要边进行切断，然后，你需要选择一条附加边进行切断。题目的输入包括图的节点数 N，附加边数 M，以及每条主要边和附加边的两个端点。
这个问题的解决方案是基于深度优先搜索（DFS）和最近公共祖先（LCA）的。首先，通过 DFS 构建出每个节点的深度和父节点信息，然后，对于每条附加边，找出它的两个端点的 LCA，并更新相关节点的计数。最后，通过遍历所有节点，根据每个节点的计数，计算出总的方案数。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f; int n,m,head[N],cnt = 0,dep[N],f[N][21]; // 定义全局变量，包括节点数 n，附加边数 m，每个节点的邻接表头 head，边数 cnt，每个节点的深度 dep，以及用于存储每个节点的 2^j 级祖先的数组 f int s[N]; // 定义数组 s，用于存储每个节点的计数 ll ans = 0; // 定义变量 ans，用于存储总的方案数 struct node{ int to,pre; }e[N * 2]; // 定义边的结构体，包括边的另一个端点 to 和前一条边的编号 pre void add(int x,int y) { e[++cnt].pre = head[x]; e[cnt].to = y; head[x] = cnt; // 定义函数 add，用于添加一条从 x 到 y 的边 } void dfs(int x,int fa) { dep[x] = dep[fa] + 1; for(int i = 1; i <= 20; i++) f[x][i] = f[f[x][i - 1]][i - 1]; // 计算节点 x 的每个 2^j 级祖先 for(int i = head[x]; i; i = e[i].pre) { int v = e[i].to; if(v == fa)continue; f[v][0] = x; dfs(v,x); // 对节点 x 的每个子节点进行深度优先搜索 } } int lca(int x,int y) { if(dep[x] < dep[y])swap(x,y); for(int i = 20; i >= 0; i--) { if(dep[f[x][i]] >= dep[y])x = f[x][i]; // 将节点 x 提升到和节点 y 同一深度 if(x == y)return x; } for(int i = 20; i >= 0; i--) { if(f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; // 同时提升节点 x 和节点 y，直到它们的祖先相同 } } return f[x][0]; // 返回节点 x 和节点 y 的最近公共祖先 } void sum(int x,int fa) { for(int i = head[x]; i; i = e[i].pre) { int v = e[i].to; if(v == fa) continue; sum(v,x); s[x] += s[v]; // 对节点 x 的每个子节点进行深度优先搜索，并更新节点 x 的计数 } } int main() { scanf("%d %d",&n,&m); // 读入节点数 n 和附加边数 m for(int i = 1; i < n; i++) { int x,y; scanf("%d %d",&x,&y); // 读入每条主要边的两个端点 add(x,y);add(y,x); // 添加两条边，分别是从 x 到 y 和从 y 到 x } dfs(1,0); // 从节点 1 开始进行深度优先搜索 for(int i = 1; i <= m; i++) { int x,y; scanf("%d %d",&x,&y); // 读入每条附加边的两个端点 int t = lca(x,y); // 计算节点 x 和节点 y 的最近公共祖先 s[t] -= 2; s[x]++,s[y]++; // 更新相关节点的计数 } sum(1,0); // 从节点 1 开始进行深度优先搜索，并更新每个节点的计数 for(int i = 2; i <= n; i++) { if(s[i] == 0) ans += m; // 如果节点 i 的计数为 0，那么可以选择任意一条附加边进行切断，所以方案数增加 m if(s[i] == 1) ans++; // 如果节点 i 的计数为 1，那么只有一种方案，所以方案数增加 1 } printf("%lld",ans); // 输出总的方案数 return 0; }