看到题目，想了挺长时间，发现不会，然后看着样子像是树上成段操作，所以查了下树链刨分，结果真的就是这个东西。。。
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.
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.
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 <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define N 20020
int 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 == '
');
if(ch == '-') flag = -1;
else
a += ch - '0';
while((ch = getchar()) != ' ' && ch != '
')
{
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<n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
//然后就是进行树链刨分
dfs(1,1,1);
top[1]=1;
index=0;
w[1]=0;
dfs1(1,-1);
memset(cnt1,0,sizeof(cnt1));
for(int i=n-1;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
while(top[x]!=top[y])
{
if( top[x] > 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
",ans+1);
}
return 0;
}