树上差分+lca 黑暗的锁链

//** 太久不写了，感觉很难受。。。比赛最近打得也不好，课内任务又重，还要忙着做项目。何去何从。

今天又写了一题，用了树上差分的知识。下面来整理整理。

1.首先让我们学一下lca（最小公共父节点） 

我用的是倍增来求的。总共其实就是两步：dfs打ST表预处理每个点的上面节点  lca求两点最小公共节点。lca里用了类似dp的思想。首先要知道dep[i][j]表示 i点向上跳1<<j个点后到达的点。然后想出递推关系式：dep[i][j]=dep[dep[i][j-1]][j-1]。用dfs来递推实现即可。

lca的实现其实就是 1.先将两个点化为同一层的点

                               2.寻找那一层的父节点是一样的

下面来看一下代码~

//倍增法求最近公共祖先LCA
#include<iostream>
using namespace std;

int n,m;

struct EDGE{
	int u,v,l;
	EDGE* ne;
}edge[100010];

struct NODE{
	EDGE* fir;
}node[100010];

int tot;
void my_build(int u,int v,int l){
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].l=l;
	edge[tot].ne=node[u].fir;
	node[u].fir=&edge[tot];
	tot++;
}

int ce[100010],dep[100010][20];//ce表示每个点的层数  dep[i][j]表示从第i个点向上走 1<<j (2^j) 个点到达的点位置；
/*
dep[i][j]=dep[dep[i][j-1]][j-1];  递推关系式
*/
void dfs(int u,int f){//打ST表   复杂度：nlogn
	ce[u]=ce[f]+1;
	dep[u][0]=f;
	for(int i=1;i<=19;i++){
		dep[u][i]=dep[dep[u][i-1]][i-1];//类似dp
	}
	EDGE* i=node[u].fir;
	while(i!=NULL){
		if(i->v==f){
			i=i->ne;
			continue;
		}
		dfs(i->v,u);
		i=i->ne;
	}
}

int lca(int u,int v){  //LCA   复杂度：logn
	if(ce[u]<ce[v]){
		swap(u,v);
	}
	for(int i=19;i>=0;i--){
		if(ce[dep[u][i]]>=ce[v]){
			u=dep[u][i];
		}
	}
	if(u==v)return u;
	for(int i=19;i>=0;i--){
		if(dep[u][i]!=dep[v][i]){
			u=dep[u][i];v=dep[v][i];
		}
	}
	return dep[u][0];
}


int main()
{
	cin>>n>>m;
	//建边之类...略；
	return 0;
}

2.树上差分

树上差分分两种：1.给点差分      2.给边差分  

对应着两种不一样的题意：给点操作还是给边操作。

给点操作很好理解，就是每个点加加减减。但如果要给边操作，我们无法轻松表示边呐，so我们就以点代边，每个点表示其与父节点连接的边。

看一下操纵吧~

//给每个点做差分：例如 给u->v路径上所有点+1：sum[u]++; sum[v]++; sum[lca]-=2;
//给边做差分->归结到给点做差分：sum[u]++; sum[v]++; sum[lca]-=1; sum[fa[lca]]-=1;

//差分数组求前缀和：
void my_add(int u,int fa){//差分数组求前缀和；
	EDGE* i=node[u].fir;
	while(i!=NULL){
		if(i->v==fa){
			i=i->ne;
			continue;
		}
		dfs(i->v,u);
		sum[u]+=sum[i->v];
		i=i->ne;
	}
}

//差分数组：(以给边差分为例)
while(m--){
	cin>>u>>v;
	int l=lca(u,v);
	sum[u]++;
	sum[v]++;
	sum[l]--;
	sum[dep[l][0]]--;
}

3.看题目

问题 ： 黑暗的锁链

题目描述

传说中的暗之连锁被人们称为Dark。Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现Dark呈现无向图的结构，图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N–1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断Dark的一条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你第一步切断主要边之后就已经把Dark斩为两截，你也需要切断一条附加边才算击败了Dark。

输入

第一行包含两个整数N和M。
之后N–1行，每行包括两个整数A和B，表示A和B之间有一条主要边。
之后M行以同样的格式给出附加边。

输出

输出一个整数表示答案。

样例输入 Copy

4 1
1 2
2 3
1 4
3 4

样例输出 Copy

3

提示

对于20%的数据，N≤100，M≤100。
对于100%的数据，N≤100000，M≤200000。数据保证答案不超过231–1。

这题用的就是树上差分+lca。而且是面向边的树上差分（因为是要切边）。

看代码~

#include<iostream>
using namespace std;
#define int long long 

int n,m;

struct EDGE{
	int u,v;
	EDGE* ne;
}edge[1000010];

struct NODE{
	EDGE* fir;
}node[1000010];

int tot;
void my_build(int u,int v){
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].ne=node[u].fir;
	node[u].fir=&edge[tot];
	tot++;
}

int dep[100010][20],ce[1000010];
void dfs(int u,int fa){
	ce[u]=ce[fa]+1;
	EDGE* i=node[u].fir;
	dep[u][0]=fa;
	for(int j=1;j<20;j++){
		dep[u][j]=dep[dep[u][j-1]][j-1];
	}
	while(i!=NULL){
		if(i->v==fa){
			i=i->ne;
			continue;
		}
		dfs(i->v,u);
		i=i->ne;
	}
}

int lca(int u,int v){
	if(ce[u]<ce[v]){
		swap(u,v);
	}
	for(int i=19;i>=0;i--){
		if(ce[dep[u][i]]>=ce[v]){
			u=dep[u][i];
		}
	}
	if(u==v)return u;
	for(int i=19;i>=0;i--){
		if(dep[u][i]!=dep[v][i]){
			u=dep[u][i];v=dep[v][i];
		}
	}
	return dep[u][0];
}

int sum[1000010];
void my_add(int u,int fa){
	EDGE* i=node[u].fir;
	while(i!=NULL){
		if(i->v==fa){
			i=i->ne;
			continue;
		}
		my_add(i->v,u);//注意不是dfs（找了很久的bug...）
		sum[u]+=sum[i->v];
		i=i->ne;
	}
}

signed main()
{
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		my_build(u,v);
		my_build(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		int l=lca(u,v);
		sum[u]++;sum[v]++;
		sum[l]-=2;
	}
	my_add(1,0);
	int ans=0;
	for(int i=2;i<=n;i++){
		if(sum[i]==0){
			ans+=m;//注意是+m！！！
		}else if(sum[i]==1){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}