题意：给定图G的一颗生成树，然后求最小割边集的大小，要求割边集中要有且仅有一条生成树边
考虑给定的生成树，求出要把某个子树和其父节点分开的最少割边数，然后枚举除了以外的最小值+1就是答案了。转换为求将每个子树要分开的最小割边。就是求这颗子树连接到子树外的边的数量。如果一条边来说它连接到非它本身子树的另外子树的贡献是1，如果要将这个点和其父节点分开，那么删除的贡献+1，但是注意到边是两条边会遍历两次。并且这个点的要删除的边。贡献-1。但是遍历两次，所以刚好减去两次。
#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;}
，闲淡时光里徜徉书海。本文是旅游开心句子说说心情，希望对大家有帮助！
