看到题目，想了挺长时间，发现不会，然后看着样子像是树上成段操作，所以查了下树链刨分，结果真的就是这个东西。。。

Minimum Cut

Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others)

Total Submission(s): 453    Accepted Submission(s): 180

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

1 4 5 1 2 2 3 3 4 1 3 1 4

 

 

Sample Output

Case #1: 2

 

 

Source

 

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 20020int n,m;struct node{	int to,next;}edge[2*N];int pre[N],cnt;int siz[N],son[N],top[N],dep[N],fa[N],w[N];int index;int cnt1[N];void add_edge(int u,int v){	edge[cnt].to=v;	edge[cnt].next=pre[u];	pre[u]=cnt++;}void dfs(int s,int deep,int father){	dep[s]=deep;	siz[s]=1;	fa[s]=father;	int mx=-1;	son[s]=0;	for(int p=pre[s];p!=-1;p=edge[p].next)	{		int v=edge[p].to;		if(v==father) continue;		dfs(v,deep+1,s);		if(siz[v]>mx)		{			mx=siz[v];			son[s]=v;		}		siz[s]+=siz[v];	}}void dfs1(int s,int father){	if(son[s]!=0)	{		w[ son[s] ]=++index;		top[ son[s] ]=top[s];		dfs1(son[s],s);	}	for(int p=pre[s];p!=-1;p=edge[p].next)	{		int v=edge[p].to;		if(v==father||v==son[s]) continue;		w[v]=++index;		top[v]=v;		dfs1(v,s);	}}int Scan()     //输入外挂{	  int res=0,ch,flag=0;	  if((ch=getchar())=='-')		  flag=1;	  else if(ch>='0'&&ch<='9')		  res=ch-'0';	  while((ch=getchar())>='0'&&ch<='9')			res=res*10+ch-'0';	  return flag?-res:res; }void Out(int a)//输出外挂{	if(a>9)		Out(a/10);	putchar(a%10+'0');}int in(){    int flag = 1;    char ch;    int a = 0;    while((ch = getchar()) == ' ' || ch == '\n');    if(ch == '-') flag = -1;    else    a += ch - '0';    while((ch = getchar()) != ' ' && ch != '\n')    {        a *= 10;        a += ch - '0';    }    return flag * a;}//你卡这个复杂度真的好吗，不过也怪自己学的少。int main(){	int T;	scanf("%d",&T);	int tt=1;	while(T--)	{		memset(pre,-1,sizeof(pre));		cnt=0;		scanf("%d%d",&n,&m);		for(int i=0;i
           
             top[y] ) { cnt1[w[top[x]] ]++; cnt1[w[x]+1]--; x = fa[ top[x] ]; } else { cnt1[ w[ top[y] ] ]++; cnt1[ w[y]+1 ]--; y = fa[ top[y] ]; } } if(dep[x] < dep[y]) { cnt1[ w[son[x] ] ]++; cnt1[ w[y]+1 ]--; } else if(dep[x] >dep[y] ) { cnt1[w[son[y]] ]++; cnt1[w[x]+1 ]--; } } int ans=10000000; for(int i=1;i<=index;i++) { cnt1[i]+=cnt1[i-1]; ans=min(ans,cnt1[i]); } printf("Case #%d: ",tt++); printf("%d\n",ans+1); } return 0;}