HDU5452

【题意】一张图G中有一颗生成树T，问最少删除多少条边能使得图不连通，删除的边中必须有且仅有一条包含生成树T中的边。

【分析】对于一个生成树上的点x，如果删除他则需要把以他为根的子树中连在外面的边数都删掉，那么这就是断开x处的花费，那么只要算出每个子树的话费即可。然后关键就是求出每个子树连向外面的边数即可：用sum[]记录。对于不在生成树中的边(u,v)由于是无向的，他会带给点u和点v各一个贡献，所以先把sum[u]++,sum[v]++,但是这样就多算了(u,v)都在同一颗子树的时候的sum值，只要让sum[lca(u,v)] -= 2就可以了(由于数据比较水，不减去也能AC，但是是错的)。然后DFS统计一遍，累加起来每个子树的sum值，像前缀和一样就是断开每颗子树需要断开的边数了。

复杂度n*log(n)+m

网赛的时候用网络流+输入挂竟然是WA，而不是超时，导致我一直往网络流想，根本没想其他方法，唉，其实蛮水的。

【AC CODE】421ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 20000+10, MAXM = 200000*2+10, MAXIN = 10000;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
int head[MAXN], tol,nxt[MAXM],to[MAXM],sum[MAXN];
inline void add_edge(int u, int v)
{
	nxt[tol] = head[u], to[tol] = v;
	head[u] = tol++;
}
int cnt, ft[MAXN], d[MAXN<<1],num[MAXN<<1];
void dfs(int u, int deep, int fa)
{
	ft[u] = cnt;
	d[cnt] = deep, num[cnt++] = u;
	for(int i = head[u]; ~i; i = nxt[i])
	{
		int v = to[i];
		if(fa == v) continue;
		dfs(v,deep+1,u);
		d[cnt] = deep, num[cnt++] = u;
	}
}
int dp[MAXN<<1][21], dp_num[MAXN<<1][21];
void st_init()
{
	rep(i,0,cnt) dp[i][0] = d[i], dp_num[i][0] = num[i];
	for(int j = 1; (1<<j) <= cnt; j++)
	{
		for(int i = 0; i+(1<<j)-1 < cnt; i++)
		{
			if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1])
			{
				dp[i][j] = dp[i][j-1];
				dp_num[i][j] = dp_num[i][j-1];
			}
			else
			{
				dp[i][j] = dp[i+(1<<(j-1))][j-1];
				dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1];
			}
		}
	}
}
int st_query(int x, int y)
{
	if(x > y) swap(x,y);
	int k = 0;
	while((1<<(k+1)) <= y-x+1) k++;
	if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k];
	return dp_num[y-(1<<k)+1][k];
}
void lca_init(int rt)
{
	cnt = 0;
	dfs(rt,0,-1);
	st_init();
}
int lca_query(int x, int y)
{
	return st_query(ft[x],ft[y]);
}
void dfs(int u, int fa)
{
	for(int i = head[u]; ~i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v,u);
		sum[u] += sum[v];
	}
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	in(t);
	while(t--)
	{
		int n,m;
		in(n),in(m);
		clc(head,-1);
		tol = 0;
		clc(sum,0);
		rep(i,1,n)
		{
			int u,v;
			in(u),in(v);
			add_edge(u,v);
			add_edge(v,u);
		}
		lca_init(1);
		rep(i,0,m-n+1)
		{
			int u,v;
			in(u),in(v);
			sum[u]++,sum[v]++;
			sum[lca_query(u,v)] -= 2;
		}
		dfs(1,0);
		int ans = INF;
		repe(i,2,n) ans = min(ans,sum[i]+1);
		printf("Case #%d: %d\n", ++count,ans);
	}
	return 0;
}
/*
1
11 22
1 2
2 3
2 4
2 5
2 6
1 7
7 8
7 9
7 10
7 11
3 4
4 5
5 6
3 5
3 6
4 8
6 11
8 9
8 10
9 10
9 11
10 11
*/