「POJ3417」Network

题意：

Dark 是一张无向图，图中有 $N$ 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 $N-1$ 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 $M$ 条附加边。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

由题目看，设一条附加边为 $(x,y)$ ，那么它肯定会与主要边构成一个环，我们在删边的过程中，如果先删掉这条附加边，那么就必须在环中 $(x,y)$ 的路径上再删掉一条主要边，这样才能使树分开。

由此可以看出，每一条附加边 $(x,y)$ 只对 $x$ 到 $y$ 路径上的主要边造成影响，我们设 $(x,y)$ 把 $x$ 到 $y$ 路径上的每一条主要边都影响了一次，可以类比得到：

如果一条主要边被影响了 $0$ 次，那么删除任意一条附加边都会使树分裂(这样的边即图中的桥)；
如果一条主要边被影响了 $1$ 次，那么只能删除影响它的附加边才会使树分裂；
如果一条主要边被影响了 $2$ 次，那么无论删除任何附加边都不会使树分裂；

所以问题转化为如下：求每条主要边被附加边覆盖了多少次。

这下就要用到树上差分了，与普通差分类比，只是把前缀和转换为了子树和，区间操作改为了路径操作，即区间两端权值修改改为树上路径端点权修改。

初始让每个点的权值为 $0$ ，对于每条非树边 $(x,y)$ ，让 $x$ 和 $y$ 的点权加 $1$ (即影响 $x$ 到 $y$ 的路径)，然后让 $LCA(x,y)$ 的点权减 $2$ (公共祖先加了 $2$ 次，由于公共祖先以上的路径不属于 $x$ 到 $y$ 之间的路径，故需要减回去，这是树上边差分)，最后 $dfs$ ，求出子树权值和，就是主要边的被覆盖次数，统计答案即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int headt[401010],heade[401010],cnt;//分别存储树边和非树边
int size[101010],fa[101010];//存储子树和(用于树上差分)，和并查集(tarjan lca)
int vis[101010],ans;
struct node
{
	int next;
	int to;
	int num;
}e[401010];
void add(int from,int to,int a[])//a[]是为了区分树边和非树边
{
	e[++cnt].next=a[from];
	e[cnt].to=to;
	a[from]=cnt;
}
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
void dfs(int u)
{
	fa[u]=u;
	vis[u]=1;
	for(int i=headt[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v])
			continue;
		dfs(v);
		fa[v]=u;
		size[u]+=size[v];
		if(size[v]==1)
			ans++;
		if(size[v]==0)//统计答案
			ans+=m;
	}
	for(int i=heade[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]==2)
		{
			int lca=getfa(v);
			size[lca]-=2;//树上差分，lca-2
		}
	}
	vis[u]=2;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b,headt);
		add(b,a,headt);
	}
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a!=b)//注意判断！！非树边可能为自环
		{
			add(a,b,heade);
			add(b,a,heade);
			size[a]++;
			size[b]++;
		}
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}