Problem Description

Given a simple unweighted graph G (an undirected graph containing no loops nor multiple edges) with n nodes and m edges. Let T be a spanning tree of G.
We say that a cut in G respects T if it cuts just one edges of T.

Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph G respecting the given spanning tree T.

 

Input

The input contains several test cases.
The first line of the input is a single integer t (1≤t≤5) which is the number of test cases.
Then t test cases follow.

Each test case contains several lines.
The first line contains two integers n (2≤n≤20000) and m (n−1≤m≤200000).
The following n−1 lines describe the spanning tree T and each of them contains two integers u and v corresponding to an edge.
Next m−n+1 lines describe the undirected graph G and each of them contains two integers u and v corresponding to an edge which is not in the spanning tree T.

 

Output

For each test case, you should output the minimum cut of graph G respecting the given spanning tree T.

 

Sample Input

 

Sample Output

 

Source

 

题意：在G中有T，问G 最小割中有且仅有一割在 T  中的最小割是多少。

 

考虑每条不属 于 T   边  对 生成树 T  树 边 的覆盖次数。

每条树边被覆盖的次数其实就是断裂这条树边后还需断裂的新边数。

 

在m-n-1行中都是T中没有的边，添加了（u， v）之后，v中的子节点，叶子节点都可以和u联系，那么在求最小割的时候就要删除这条边，使得G中 变成两个由 u 和v 构成的不连通的图。

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <cmath>

 #include <stack>

 #include <cstring>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define min(a,b) (a<b?a:b)

 #define N 100005

 vector< vector<int> > G;

 int deep[N], f[N], cnt[N];

 void dfs(int u, int fa, int step)

 {

     deep[u] = step;

     cnt[u] = ;

     f[u] = fa;

     int len = G[u].size();

     for(int i = ; i < len; i++)

     {

         int v = G[u][i];

         if(v != fa)

             dfs(v, u, step+);

     }

 }

 void Lca(int x, int y)

 {

     while(x != y)

     {

         if(deep[x] >= deep[y])

         {

             cnt[x]++;

             x = f[x];

         }

         else

         {

             cnt[y]++;

             y = f[y];

         }

     }

 }

 int main()

 {

     int t, i, a, b, n, m, l = ;

     scanf("%d", &t);

     while(t--)

     {

         G.resize(N);

         G.clear();

         scanf("%d%d", &n, &m);

         for(i = ; i < n; i++)

         {

             scanf("%d%d", &a, &b);

             G[a].push_back(b);

             G[b].push_back(a);

         }

         dfs(, , );

         for(; i <= m; i++)

         {

             scanf("%d%d", &a, &b);

             Lca(a, b);

         }

         int ans = INF;

         for(i = ; i <= n; i++)

             ans = min(ans, cnt[i]);

         printf("Case #%d: %d\n", l++, ans);

     }

     return ;

 }