HDU 5452 Minimum Cut（LCA）

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

题意：

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

思路：

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

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

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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 const int maxn = 20000+5;
  7 
  8 int n,m,tot,Log,ans;
  9 int head[maxn],degree[maxn],deep[maxn];
 10 int p[maxn][30],cut[maxn];
 11 
 12 struct node
 13 {
 14     int v,next;
 15 }e[2*200000+5];
 16 
 17 void addEdge(int u, int v)
 18 {
 19     e[tot].v = v;
 20     e[tot].next = head[u];
 21     head[u] = tot++;
 22 }
 23 
 24 void dfs(int u, int fa, int d)
 25 {
 26     deep[u]=d;
 27     p[u][0]=fa;
 28     for(int i=head[u];i!=-1;i=e[i].next)
 29     {
 30         int v=e[i].v;
 31         if(v==fa)  continue;
 32         dfs(v,u,d+1);
 33     }
 34 }
 35 
 36 void init()
 37 {
 38     for(int j=1;j<=Log;j++)
 39         for(int i=1;i<=n;i++)
 40              p[i][j]=p[p[i][j-1]][j-1];
 41 }
 42 
 43 int LCA(int x, int y)
 44 {
 45     if(x==y)  return x;
 46     if(deep[x]<deep[y])  swap(x,y);
 47     for(int i=Log;i>=0;i--)
 48     {
 49         if(deep[p[x][i]]>=deep[y])
 50             x=p[x][i];
 51     }
 52     if(x==y)  return x;
 53     for(int i=Log;i>=0;i--)
 54     {
 55         if(p[x][i]!=p[y][i])
 56         {
 57             x=p[x][i];y=p[y][i];
 58         }
 59     }
 60     return p[x][0];
 61 }
 62 
 63 
 64 void solve(int u, int fa)
 65 {
 66     cut[u] = degree[u];
 67     for(int i=head[u];i!=-1;i=e[i].next)
 68     {
 69         int v = e[i].v;
 70         if(v==fa)  continue;
 71         solve(v,u);
 72         cut[u]+=cut[v];
 73     }
 74     ans = min(ans, cut[u]);
 75 }
 76 
 77 
 78 int main()
 79 {
 80     //freopen("in.txt","r",stdin);
 81     int T;
 82     int kase = 0;
 83     scanf("%d",&T);
 84     while(T--)
 85     {
 86         tot = 0;
 87         memset(head,-1,sizeof(head));
 88         memset(degree,0,sizeof(degree));
 89         scanf("%d%d",&n,&m);
 90         for(int i=1;i<=n-1;i++)
 91         {
 92             int u,v;
 93             scanf("%d%d",&u,&v);
 94             addEdge(u,v);
 95             addEdge(v,u);
 96         }
 97 
 98         dfs(1,-1,0);
 99         for(Log=0;(1<<Log)<=n+1;Log++);
100         Log--;
101         init();
102 
103         for(int i=1;i<=m-n+1;i++)
104         {
105             int u,v;
106             scanf("%d%d",&u,&v);
107             degree[u]++;
108             degree[v]++;
109             int lca = LCA(u,v);
110             degree[lca] -= 2;
111         }
112 
113         ans = 0x3f3f3f3f;
114         solve(1,-1);
115         printf("Case #%d: %d
",++kase,ans+1);
116     }
117     return 0;
118 }