POJ3417(Network)

Network

Description

Yixght is a manager of the company called SzqNetwork(SN). Now she’s very worried because she has just received a bad news which denotes that DxtNetwork(DN), the SN’s business rival, intents to attack the network of SN. More unfortunately, the original network of SN is so weak that we can just treat it as a tree. Formally, there are N nodes in SN’s network, N-1 bidirectional channels to connect the nodes, and there always exists a route from any node to another. In order to protect the network from the attack, Yixght builds M new bidirectional channels between some of the nodes.

As the DN’s best hacker, you can exactly destory two channels, one in the original network and the other among the M new channels. Now your higher-up wants to know how many ways you can divide the network of SN into at least two parts.

Input

The first line of the input file contains two integers: N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) — the number of the nodes and the number of the new channels.

Following N-1 lines represent the channels in the original network of SN, each pair (a,b) denote that there is a channel between node a and node b.

Following M lines represent the new channels in the network, each pair (a,b) denote that a new channel between node a and node b is added to the network of SN.

Output

Output a single integer — the number of ways to divide the network into at least two parts.

Sample Input

4 1
1 2
2 3
1 4
3 4
Sample Output

3

思路

LCA + 树上差分

先以主边建立图然后做ST倍增的预处理，预处理完之后再来分析m条附加边

1. 假如x – y有一条附加边，那么x – LCA – y这个子树就会形成一个环，那么切掉这条x – y的附加边还需要切掉x – LCA这条边 或者 LCA – y这条边才能使得图不连通。

2. 其他主边（除去环以外的边）只要随便切掉一条都可以使得图不连通，那么可以随意切掉任意一条附加边。

3. 如果x – y有两条附加边那么在这个环中切掉任何一个主边 和 一条附加边图依然连通。

然后对m次读入操作做一个树上差分，假如x – y之间有一条边，那么受到影响必将是x – LCA – y这个环中的主边，所以我们对这个环中的主边进行树上差分。diff[x]++；diff[y]++；diff[LCA(x,y)] -= 2,用子节点的序号替代 父 – 子这条边。每加入一条附加边即对两个点进行+1标记，LCA点进行-2。m条附加边读入完毕之后再根据上面的分析就可以得到三种情况：

1. 主边没有被标记过，也就是说这条主边不在任何一个环中，那么附加边可以随便删一条，ans += m

2. 主边被标记过一次，也就是说这条主边在一个环中而且这个环中有且只有一条附加边，那么删掉这条主边再删掉这条环中的附加边才能使得图不连通，ans++；

3. 主边被标记次数2次以上，也就说这条主边在至少一个环中而且删掉这条主边再删掉这删掉一条附加边图依然连通，这种情况无解。

diff[x]++；diff[y]++；diff[LCA(x,y)] -= 2；x – LCA这个路径上的主边覆盖次数+1，y – LCA这个路径上的主边覆盖次数+1，diff[LCA(x,y)] -= 2，点 x 和 点y 和 点 LCA，都试着沿路径一直回到树根处（不是回到LCA而是回到树根），x的路径中每经过一个点，就将这些点上的值加上diff[x]，同样y的路径上没经过一个点就将这些点上的值加上diff[y]，LCA也是这样。然后惊人的发现回到树根的部分，其实被抵消掉了diff值没有变化，而x到LCA，y到LCA部分的值都已经分别加上了diff[x]，diff[y]。终究还是离不开那句话受到影响的主边只是 x – LCA – y这个环中的主边。最后跑一遍递归从根节点跑dfs，把标记次数累加的形式依次往上传。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100005;
const int maxd = 19;
struct edge{
	int to;
	int next;
}e[maxn<<1];
int head[maxn];
int dep[maxn];
int f[maxn][20];
int diff[maxn];
bool vis[maxn];
int sum[maxn];
int tot;
void clear_set()
{
	memset(diff,0,sizeof(diff));
	memset(head,-1,sizeof(head));
	memset(sum,0,sizeof(sum));
	memset(vis,false,sizeof(vis));
	memset(f,0,sizeof(f));
	memset(dep,0,sizeof(dep));
}
inline void addedge(int x,int y)
{
	e[tot].to = y;
	e[tot].next = head[x];
	head[x] = tot++;
}
void dfs(int x,int fx)
{
	dep[x] = dep[fx] + 1;
	f[x][0] = fx;
	for(int i = 1;i <= maxd;i++){
		f[x][i] = f[f[x][i-1]][i-1];
	}
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(y == fx)		continue;
		dfs(y,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x] < dep[y])		swap(x,y);
	int d = dep[x] - dep[y];
	for(int i = 0;i <= maxd;i++){
		if(((1<<i)&d)){
			x = f[x][i];
		}
	}
	if(x == y)		return x;
	for(int i = maxd;i >= 0;i--){
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
void ans(int x)
{
	vis[x] = true;
	sum[x] = diff[x];
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(vis[y])	continue;
		ans(y);
		sum[x] += sum[y];
	}
}
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		tot = 0;clear_set();
		int x,y;
		for(int i = 1;i < n;i++){
			scanf("%d%d",&x,&y);
			addedge(x,y);	addedge(y,x);
		}
		dfs(1,0);
		for(int i = 0;i < m;i++){
			scanf("%d%d",&x,&y);
			int r = LCA(x,y);
			diff[x]++;diff[y]++;
			diff[r] -= 2;
		}
		ans(1);
		int res = 0 ;
		for(int i = 2;i <= n;i++){			//1是根节点忽略，因为是用子节点表示父->子 这条边
			if(sum[i] == 0){			//主边标记次数0次，附加边随意删
				res += m;
			}
			if(sum[i] == 1){			//主边标记次数1次，只有删所在环的附加边的一种可能
				res++;
			}
		}
		printf("%d\n",res);
	}
	return 0;
} 

愿你走出半生，归来仍是少年~