题目链接：
题目描述：
有一棵生成树，有n个点，给出m-n+1条边，截断一条生成树上的边后，再截断至少多少条边才能使图不连通， 问截断总边数？
解题思路：
因为只能在生成树上截断一条边(u, v)，所以只需要统计以v为根节点的子生成树里的节点与子生成树外的节点的边数就可以了。对于新加入的边(u', v')来说，只影响以LCA(u, v)为根节点的子树里面的节点。统计所有答案，扫一遍输出最小即可。(比赛的时候只统计叶子节点，给水过去了........23333333)
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 const int maxn = 20010; 9 struct node 10 { 11 int to, next; 12 }edge[maxn*2]; 13 int tot, head[maxn], deep[maxn], fa[maxn], ans[maxn]; 14 15 void init () 16 { 17 tot = 0; 18 memset (head, -1, sizeof(head)); 19 } 20 21 void Add (int from, int to) 22 { 23 edge[tot].to = to; 24 edge[tot].next = head[from]; 25 head[from] = tot ++; 26 } 27 28 void dfs (int u, int father, int dep) 29 { 30 deep[u] = dep; 31 ans[u] = 1; 32 fa[u] = father; 33 34 for (int i=head[u]; i!=-1; i=edge[i].next) 35 { 36 int v = edge[i].to; 37 if (v != father) 38 dfs (v, u, dep+1); 39 } 40 } 41 42 void LCA (int x, int y) 43 { 44 while (x != y) 45 { 46 if (deep[x] >= deep[y]) 47 { 48 ans[x] ++; 49 x = fa[x]; 50 } 51 else 52 { 53 ans[y] ++; 54 y = fa[y]; 55 } 56 } 57 } 58 59 int main () 60 { 61 int t, n, m, i; 62 scanf ("%d", &t); 63 64 for (int j=1; j<=t; j++) 65 { 66 init (); 67 int u, v; 68 scanf ("%d %d", &n, &m); 69 70 for (i=1; i<n; i++) 71 { 72 scanf ("%d %d", &u, &v); 73 Add (u, v); 74 Add (v, u); 75 } 76 dfs (1, 0, 1); 77 78 for ( ;i<=m; i++) 79 { 80 scanf ("%d %d", &u, &v); 81 LCA (u, v); 82 } 83 84 int res = INF; 85 for (i=2; i<=n; i++) 86 res = min (res, ans[i]); 87 printf ("Case #%d: %d ", j, res); 88 } 89 return 0; 90 }