HDU 5452 Minimum Cut（LCA）

http://acm.hdu.edu.cn/showproblem.php?pid=5452

题意：

有一个连通的图G，先给出图中的一棵生成树，然后接着给出图中剩余的边，现在要删除最少的边使得G不连通，并且在生成树中必须且只能删除一条边。

思路：

最简单的情况是G就是给出的生成树，这种情况下删除任何一条边都可以。

枚举每一条树边，如果该边的子节点没有非树边，那么删除这条边就可以使图非连通，如果有非树边，那么就要把非树边删去，当然，子节点之内的非树边不用删，要删的是连出去的非树边。

这样一来，对每个顶点记录非树边的度数，表示要删除的情况，但是如果在一棵子树内怎么办呢？此时就会多算，求得它们的lca，在该顶点上度数-2，也就是减去这条边。最后dfs一遍即可。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn = +;

 int n,m,tot,Log,ans;

 int head[maxn],degree[maxn],deep[maxn];

 int p[maxn][],cut[maxn];

 struct node

 {

     int v,next;

 }e[*+];

 void addEdge(int u, int v)

 {

     e[tot].v = v;

     e[tot].next = head[u];

     head[u] = tot++;

 }

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

 {

     deep[u]=d;

     p[u][]=fa;

     for(int i=head[u];i!=-;i=e[i].next)

     {

         int v=e[i].v;

         if(v==fa)  continue;

         dfs(v,u,d+);

     }

 }

 void init()

 {

     for(int j=;j<=Log;j++)

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

              p[i][j]=p[p[i][j-]][j-];

 }

 int LCA(int x, int y)

 {

     if(x==y)  return x;

     if(deep[x]<deep[y])  swap(x,y);

     for(int i=Log;i>=;i--)

     {

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

             x=p[x][i];

     }

     if(x==y)  return x;

     for(int i=Log;i>=;i--)

     {

         if(p[x][i]!=p[y][i])

         {

             x=p[x][i];y=p[y][i];

         }

     }

     return p[x][];

 }

 void solve(int u, int fa)

 {

     cut[u] = degree[u];

     for(int i=head[u];i!=-;i=e[i].next)

     {

         int v = e[i].v;

         if(v==fa)  continue;

         solve(v,u);

         cut[u]+=cut[v];

     }

     ans = min(ans, cut[u]);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     int kase = ;

     scanf("%d",&T);

     while(T--)

     {

         tot = ;

         memset(head,-,sizeof(head));

         memset(degree,,sizeof(degree));

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

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

         {

             int u,v;

             scanf("%d%d",&u,&v);

             addEdge(u,v);

             addEdge(v,u);

         }

         dfs(,-,);

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

         Log--;

         init();

         for(int i=;i<=m-n+;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             degree[u]++;

             degree[v]++;

             int lca = LCA(u,v);

             degree[lca] -= ;

         }

         ans = 0x3f3f3f3f;

         solve(,-);

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

     }

     return ;

 }