hdu 5452 Minimum Cut 求最小割边集的大小

题意：给定图G的一颗生成树，然后求最小割边集的大小，要求割边集中要有且仅有一条生成树边

考虑给定的生成树，求出要把某个子树和其父节点分开的最少割边数，然后枚举除了$root$以外的最小值+1就是答案了。

转换为求将每个子树要分开的最小割边。就是求这颗子树连接到子树外的边的数量。

如果一条边$e(u,v)$不是树边，那么对于$u$和$v$来说它连接到非它本身子树的另外子树的贡献是1，如果要将这个点和其父节点分开，那么删除的贡献+1，但是注意到边是两条边会遍历两次。

并且$e(u,v)$这条边并不是$lca(u,v)$这个点的要删除的边。贡献-1。但是遍历两次，所以刚好减去两次。

//author: CHC
//First Edit Time:	2015-09-19 19:43
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=20000 + 1000;
const int MAXM=200000*2 + 10000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
    int to,next,flag;
    Edge(){}
    Edge(int _to,int _next,int _flag):to(_to),next(_next),flag(_flag){}
}e[MAXM];
int head[MAXN],tot;
void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}
void AddEdge(int u,int v,int flag){
    e[tot]=Edge(v,head[u],flag);
    head[u]=tot++;
    e[tot]=Edge(u,head[v],flag);
    head[v]=tot++;
}
int fa[MAXN][22],dep[MAXN];
void dfs(int u,int father){
    fa[u][0]=father;
    for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(e[i].flag&&!dep[v]){
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    int x=dep[a]-dep[b],y=0;
    while(x){
        if(x&1)a=fa[a][y];
        x>>=1;
        ++y;
    }
    if(a==b)return a;
    for(int i=20;i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int ans[MAXN],delta[MAXN];
void dfs1(int u,int father){
    ans[u]=delta[u]=0;
    //printf("u:%d\n",u);
    //system("pause");
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        //printf("%d-->%d %d\n",u,v,e[i].flag);
        if(e[i].flag){
            //printf("%d:%d\n",v,father);
            if(v!=father){
                //printf("%d-->%d\n",u,v);
                //printf("v:%d\n",v);
                dfs1(v,u);
                //printf("%d:%d\n",u,ans[v]);
                ans[u]+=ans[v];
            }
        }
        else {
            ans[u]++;
            //printf("before:\n");
            ans[lca(u,v)]--;
            //printf("after:\n");
        }
    }
    //printf("%d\n",ans[u]);
}
int main()
{
    int T,n,m,cas=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=0,x,y;i<m;i++){
            scanf("%d%d",&x,&y);
            AddEdge(x,y,(i<(n-1)));
            //printf("%d-->%d %d\n",x,y,i<(n-1));
        }
        dep[1]=1;
        dfs(1,1);
        dfs1(1,1);
        //printf("here");
        //for(int i=1;i<=n;i++)printf("%d %d\n",i,ans[i]);
        //puts("");
        int minn=INF;
        for(int i=2;i<=n;i++)minn=min(minn,ans[i]+1);
        printf("Case #%d: %d\n",++cas,minn);
    }
    return 0;
}
/*

*/