树链剖分

题目描述#

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式#

第一行包含三个正整数，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来行每行包含两个正整数，表示结点和结点之间有一条直接连接的边（数据保证可以构成树）。

接下来行每行包含两个正整数，表示询问结点和结点的最近公共祖先。

输出格式#

输出包含行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1#

样例输入 #1#

plaintext

样例输出 #1#

plaintext

提示#

对于的数据，，。

样例说明：

该树结构如下：

第一次询问：的最近公共祖先，故为。

第二次询问：的最近公共祖先，故为。

第三次询问：的最近公共祖先，故为。

第四次询问：的最近公共祖先，故为。

第五次询问：的最近公共祖先，故为。

故输出依次为。

算法分析
模板

{% raw %}

{% endraw %}

此算法需要两次

第一次完成找重儿子,子树大小,深度,父子关系的任务
我们不妨令1号结点为树根,进行,即可完成

void dfs_1(int u,int f){
    fa[u]=f,size[u]=1;
    depth[u]=depth[f]+1;
    int t=-1;
    for(int i = 0;i<ro[u].size();i++){
        if(ro[u][i]==f) continue;
        dfs_1(ro[u][i],u);
        size[u]+=size[ro[u][i]];
        if(size[ro[u][i]]>t){
            t=size[ro[u][i]],son[u]=ro[u][i];
        }
    }
}

cpp

第二次,则要处理出每个点其重链所在的链头,以及序通过代码及图示可以发现重链剖分的一此性质: 通过代码及图示可以发现重链剖分的一些性质:

所有重链互不相交,即每个点只属于一条重链
所有重链长度和等于节点数(链长指链上节点数)
一个点到根节点的路径上经过的边中轻边最多只有log条

前两个性质好理解,那么第三个性质是为什么呢?因为最坏情况就是这个点到根路径上经过的边都是轻边,
那么每走一条轻边到达这个点的父节点就代表这个父节点至少还有一个与当前子树同样大的子树,也就是说每走一条轻边走到的点的子树
大小就要*2,因此最多只能走次。这也是为什么要选重儿子而不是随便一个儿子的原因。

void dfs_2(int u,int f){
    top[u]=f;
    id[u]=++cnt;
    w[cnt]=b[u];
    if(!son[u]) return;
    dfs_2(son[u],f);
    for(int i = 0;i<ro[u].size();i++){
        if(ro[u][i]==fa[u]||ro[u][i]==son[u])continue;
        dfs_2(ro[u][i],ro[u][i]);
    }
}

cpp

对于求的,可以每次优先爬点所在重链链头深的点,如果两个点不在同一条重链上,那么直接把链头深的点跳到链头,
重复这个过程,直到两个点处在同一条重链上,直接输出深度浅的点就是了。
因为重链是直接跳到链头,时间复杂度是的,而跳轻边最多就条,因此, 求两个点的时间复杂度是

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        x=fa[top[x]];
    }return depth[x]<depth[y]? x:y;
}

cpp

{% raw %}

{% endraw %}

{% raw %}

{% endraw %}


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
vector <int> ro[MAXN];
int cnt,fa[MAXN],size[MAXN],depth[MAXN],son[MAXN],top[MAXN],id[MAXN],w[MAXN],b[MAXN];
void dfs_1(int u,int f){
    fa[u]=f,size[u]=1;
    depth[u]=depth[f]+1;
    int t=-1;
    for(int i = 0;i<ro[u].size();i++){
        if(ro[u][i]==f) continue;
        dfs_1(ro[u][i],u);
        size[u]+=size[ro[u][i]];
        if(size[ro[u][i]]>t){
            t=size[ro[u][i]],son[u]=ro[u][i];
        }
    }
}
void dfs_2(int u,int f){
    top[u]=f;
    id[u]=++cnt;
    w[cnt]=b[u];
    if(!son[u]) return;
    dfs_2(son[u],f);
    for(int i = 0;i<ro[u].size();i++){
        if(ro[u][i]==fa[u]||ro[u][i]==son[u])continue;
        dfs_2(ro[u][i],ro[u][i]);
    }
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        x=fa[top[x]];
    }return depth[x]<depth[y]? x:y;
}
int main(){
    int N=read(),M=read(),S=read(),u,v;
    N--;
    for(;N--;){
        cin>>u>>v;
        ro[u].push_back(v);
        ro[v].push_back(u);
    }
    dfs_1(S,0);
    dfs_2(S,S);
    for(;M--;){
        cin>>u>>v;
        cout<<LCA(u,v)<<endl;
    }
    return 0;
}

cpp

{% raw %}

{% endraw %}

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

Comments