题干：
Given a simple unweighted graph GG (an undirected graph containing no loops nor multiple edges) with nn nodes and mm edges. Let TT be a spanning tree of GG.
We say that a cut in GG respects TT if it cuts just one edges of TT.
Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph GG respecting the given spanning tree TT.
Input
The input contains several test cases.
The first line of the input is a single integer t (1≤t≤5)t (1≤t≤5) which is the number of test cases.
Then tt test cases follow.
Each test case contains several lines.
The first line contains two integers n (2≤n≤20000)n (2≤n≤20000) and m (n−1≤m≤200000)m (n−1≤m≤200000).
The following n−1n−1 lines describe the spanning tree TT and each of them contains two integers uu and vv corresponding to an edge.
Next m−n+1m−n+1 lines describe the undirected graph GG and each of them contains two integers uu and vv corresponding to an edge which is not in the spanning tree TT.
Output
For each test case, you should output the minimum cut of graph GG respecting the given spanning tree TT.
Sample Input
1
4 5
1 2
2 3
3 4
1 3
1 4 Sample Output
Case #1: 2 题目大意：
给你一个图G，n个点m条边，图中给定一颗生成树（前n-1条输入的边）。问一个最小割的边数量（将图变成一个不连通图），要求需要包含给定生成树内的一条边。
解题报告：
因为有一条生成树内的边必选，所以这是个切入点，我们枚举生成树上的每一条边<U,V>，假设我们要删的边是<U,V>， 那么自然图就分成了两块，这也正是我们要的结果。我们所要做的就是让V的子树上的任何节点，不再和其V子树外的其他节点相连。使得他们完全分离开。
有了这个思路之后，就需要换一个角色重新考虑问题了，站在新加入的边的角度上看：对于每一条新加入的一条树T外的边<a,b>, 那么我们需要判断枚举到哪一条T内的边的时候，需要将这条边删除掉，不难观察出来，是ab两点相连的这条链上的边，那么树上维护这条链上的边计数+1，就转化成有根树然后树上差分即可。
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e4 + 5;
int n,m,val[MAX];
struct Edge {
int u,v;
int ne;
} e[MAX*20];
int tot;
int head[MAX],f[MAX];
int fa[MAX][33],dep[MAX];
void add(int u,int v) {
e[++tot].u = u;
e[tot].v = v;
e[tot].ne = head[u];
head[u] = tot;
}
void dfs(int cur,int rt) {
fa[cur][0] = rt;
dep[cur] = dep[rt] + 1;
for(int i = head[cur]; ~i; i = e[i].ne) {
int v = e[i].v;
if(v == rt) continue;
dfs(v,cur);
}
for(int i = 1; i<=31; i++) {
fa[cur][i] = fa[fa[cur][i-1]][i-1];
}
}
int lca(int u,int v) {
if(dep[u] < dep[v]) swap(u,v);
int dc = dep[u] - dep[v];
for(int i = 0; i<=31; i++) {
if((1<<i) & dc) u = fa[u][i];
}
if(u == v) return u;
for(int i = 31; i>=0; i--) {
if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
}
return fa[u][0];
}
int ans = 0x3f3f3f3f;
void DFS(int cur,int rt) {
for(int i = head[cur]; ~i; i = e[i].ne) {
if(e[i].v == rt) continue;
DFS(e[i].v,cur);
val[cur] += val[e[i].v];
}
if(cur != 1) ans = min(ans,val[cur]);
}
int main()
{
int t,iCase=0;
cin>>t;
while(t--) {
scanf("%d%d",&n,&m);
tot=0,ans=0x3f3f3f3f;
for(int i = 1; i<=n; i++) head[i] = -1,val[i]=0;
for(int u,v,i = 1; i<=n-1; i++) {
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0);
for(int u,v,i = n; i<=m; i++) {
scanf("%d%d",&u,&v);
val[u]++,val[v]++;val[lca(u,v)]-=2;
}
DFS(1,0);
printf("Case #%d: %d\n",++iCase,ans+1);
}
return 0 ;
} 另一个解题报告：https://blog.csdn.net/cqbztsy/article/details/50706555
树形dp做法：https://www.cnblogs.com/qscqesze/p/4822468.html
对于这个点，如果要消除他和他父亲之间的联系的话，代价就是他的子树所有连向外界的边就好了
跑一遍dfs维护一下就行了。
（但是好像证明是不对的
2
4 4 1 2 2 3 3 4 1 3
4 4 1 3 2 3 2 4 1 2
这组数据，应该是1 1，但是下面这个代码输出的是1 2）
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 20050
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
//*********************************************************************************
vector<int> Q[maxn];
vector<int> E[maxn];
int vis[maxn];
int dp[maxn];
int ans;
void dfs(int x)
{
vis[x]=1;
for(int i=0;i<Q[x].size();i++)
{
int y=Q[x][i];
dfs(Q[x][i]);
dp[x]+=dp[y]-1;
}
ans = min(ans,dp[x]);
for(int i=0;i<E[x].size();i++)
if(vis[E[x][i]])
dp[E[x][i]]--;
vis[x]=0;
}
int main()
{
int t;scanf("%d",&t);
for(int cas = 1;cas<=t;cas++)
{
ans = 99999999;
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
Q[i].clear(),E[i].clear();
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
for(int i=0;i<n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
dp[x]++,dp[y]++;
if(x>y)swap(x,y);
Q[x].push_back(y);
}
for(int i=n-1;i<m;i++)
{
int x,y;scanf("%d%d",&x,&y);
dp[x]++,dp[y]++;
if(x>y)swap(x,y);
E[y].push_back(x);
}
dfs(1);
printf("Case #%d: %d\n",cas,ans);
}
}
京公网安备 11010502036488号