备战蓝桥杯---树学初步1

LCA（最近公共祖先）

定义：有根树的两个节点u,v，他们的LCA是一个节点x,其中x是他们的公共祖先并且X的深度尽可能大。

法1---Tarjan算法：

核心：DFS+并查集

在并查集中建立仅有u的集合，设该集合祖先为u，对于他的每一个孩子v：dfs(v)

合并v到父节点u的集合，设置u为已遍历。

有点抽象，来看看图例吧：

首先，一开始每一个点的fa都是自己，然后遍历到11，它没有儿子，设置11为已遍历并指向5，然后到12，此时若有11与12的询问就是11的fa，标记12并到5，5指2并标记，依次类推即可

注意，这要把所有询问提前记录下来（即离线操作）

下面是模板代码：

#include<bits/stdc++.h>
using namespace std;
int fa[100000];
vector<int> a[100000];
int que[1000][1000];
bool vis[100000];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	fa[x]=y;
}
void dfs(int x,int fa){
	for(int i=0;i<a[x].size();i++){
		int y=a[x][i];
		dfs(y,x);
		merge(y,x);
	}
	vis[x]=1;
	for(int i=1;i<=n;i++){
		if(vis[i]&&que[x][i]){
			int tmp=find(i);
			cnt[tmp]+=que[x][i];
			que[x][i]=que[i][x]=0;
		}
	}
}

法2--通过DFS序转化成RMQ问题

对有根树DFS，按照遍历顺序记录2*N-1的序列即欧拉序列

我们发现两个数（u，v)（前面的先出现）的LCA就是最后一次出现的u和第一次出现的v中间的数就是从u--v的路径，而其中深度最低（包含自己）的就是其LCA。

因此我们求一个min即可，其中我们为了方便可以从第一次出现的u开始（其子树不影响）

怎么求RMQ?

1.线段树。

2.ST。

线段树大家都知道，那么就看一下ST吧

In a word,ST就是DP+倍增

我们用f[i][j]表示[i,i+2^j-1]的min,f[i][0]=a[i],因此，f[i][j]=min(f[i][j-1],f[i+2^(j-1),][j-1])

当我们要查询时，对于[10,20],我们可以先得到[10,18]的min与[19,20]（根据2进制看）

我们也可以[10,18]以及[12,20]。

下面是模板代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int b[N],dp[N][N];
void rmq_st(int n){
	for(int i=1;i<=n;i++) dp[i][0]=b[i];
	int m=(int)(log(1.0*n)/log(2.0));
	for(int j=1;j<=m;j++){
		int t=n-(1<<j)+1;
		for(int i=1;i<=t;i++){
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
}
int rmp_find(int l,int r){
	int k=(int)(log(1.0*(r-l+1))/log(2.0));
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}

接下来我们看看如何编号。

我们用DFN序编号即可以（直接按照深度存的话对于一个深度可能有很多对应）

下面是实现代码：

void dfs(int x,int fa){
	int tmp=++num;
	b[++cnt]=tmp;//以DFS代替的欧拉序 
	f[tmp]=x;//实现从DFS序到真实点的映射 
	first[x]=cnt;//记录x第一次出现的位置 
	for(int i=head[x];i!=-1;i=edge[i].next){
		int v=edge[i].dian;
		if(v==fa) continue;
		dfs(v,x);
		b[++cnt]=tmp;
	}
}
int LCA(int a,int b){
	if(first[a]>first[b]) swap(a,b);
	int k=rmq_find(first[a],first[b]);
	return f[k];
}

下面介绍一下如何求两个点的距离算是应用吧：

每一个点到根的距离-2*LCA到根的距离。

下面介绍介绍常见的3种“dfs序”

欧拉序：每经过一点记录一次的序列

DFS序：记录进栈与出栈的序列。

DFN序：只记录进栈的序列。

对于这个图：

欧拉序：12552.....DFS序：1255662379.。。。DFN序（时间戳）：12563....

对于时间戳：

125637948，我们记录一下每一个子树的最大时间（即最后进栈），我们发现对于256，379，任何一个子树在其中都是连着并不重复出现的，而当我们知道一个子树的最大时间就知道了对应的区间。

这有什么用呢？

在树上1.修改x变成Y,2.查以x为根的子树的权值和。

这就转化成了区间和的问题，对DFN序再用树状数组维护即可。

我们来个应用吧：

我们先按DFN，我们发现一个点要么跟父亲一样，要么是一个从来没有出现的点，这个就是合法的，于是我们令dp[i][j]表示走到i时用了j种颜色的方案数，易得状态转移方程：

dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(k-j+1).

下面是AC代码：

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,y,k,x;
long long dp[400][400];
int main(){
    cin>>n>>k;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(k-j+1))%mod;
        }
    }
    long long ans=0;
    for(int i=1;i<=k;i++) ans=(ans+dp[n][i])%mod;
    cout<<ans;
}