给你一个图G，图中包含一颗生成树。要求只能删除生成树内的一条边，使得图不联通。问最小的删除边数量。
题目解析：
对于生成树上的一条边<U,V>, 假设我们要删的边是<U,V>， 那么我们所要做的就是让V的子树上的任何节点，不再和其V子树外的其他节点相连。使得他们完全分离开。
假设新加入的一条树T外的边<a,b>, 那么我们需要判断哪些点需要将这条边删除掉。需要删除这个边的点就是LCA（a,b）路径上的上的所有点。
========================================================================================================================
#include <iostream> #include <cmath> #include <algorithm> #include <string> #include <deque> #include <cstring> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <cstdlib> using namespace std; typedef long long LL; const LL INF = 0xffffff; const int maxn = 201315; const LL MOD = 1e9+7; vector<vector<int> >G; int Father[maxn], Deep[maxn], ans[maxn]; int n, m; void Init() { G.clear(); G.resize(n+2); memset(Deep, 0, sizeof(Deep)); memset(ans, 0, sizeof(ans)); memset(Father, 0, sizeof(Father)); } void DFS(int fa,int cur,int deep) { Father[cur] = fa; Deep[cur] = deep; int len = G[cur].size(); for(int i=0; i<len; i++) { int v = G[cur][i]; if(v != fa) { DFS(cur, v, deep+1); } } } void LCA(int a,int b) { if(a == b) { // ans[a] -= 2; return ; } if(Deep[a] > Deep[b]) { ans[a] ++; LCA(Father[a], b); } else { ans[b] ++; LCA(a, Father[b]); } } int main() { int T, cas = 1, a, b; scanf("%d", &T); while(T--) { scanf("%d %d",&n, &m); Init(); for(int i=1; i<=n-1; i++) { scanf("%d %d", &a, &b); G[a].push_back(b); G[b].push_back(a); } DFS(0, 1, 0); for(int i=n; i<=m; i++) { scanf("%d %d",&a, &b); LCA(a, b); } int res = INF; for(int i=2; i<=n; i++) res = min(res, ans[i]); printf("Case #%d: %d ", cas++, res+1); } return 0; }