1. 何谓LCA

LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

img

如图,1和7的公共祖先有5和10,而它们的LCA是5。

2. 怎么求LCA

题设:求节点a,b的LCA

思路1:从节点a遍历到根节点,再从b遍历到根节点,找到最先相遇的地方。复杂度:o(n)

思路2:倍增。具体怎么做底下讲。复杂度:o(log n)

3. 倍增求LCA

做法:程序开始时选取任意节点为树根,进行dfs,得到所有点的深度与pre[i][j]。何谓pre[i][j]?

pre[i][j]指节点i的第2的j次方个祖先

img2

如上图中,10的第1个祖先是9,第二个祖先是8,第三个祖先是7,第四个祖先是1。所以10的第2的0次方个祖先是9(2^0=1),10的第2的1次方个祖先是8(2^1=2),10的第2的2次方个祖先是1(2^2=4)。很显然,10没有2的3次方个祖先。所以pre[10][0]=9,pre[10][1]=8,pre[10][2]=1。

而且通过倍增的思想,我们不难发现i的第2的j次方个祖先就是i的第2的j-1次方个祖先的第2的j-1次方个祖先(不信你看图),所以pre[i][j]=pre[pre[i][j-1]][j-1]。

其实要搞懂这个也很简单
2^i = 2*2^(i-1) = 2^(i-1) + 2^(i-1)

懂了吧
所以:
i的第2的j次方个祖先就是i的第2的j-1次方个祖先的第2的j-1次方个祖先

有了这个规律,我们就可以在dfs中预处理所有的pre了!

而求LCA的思路就是:对于节点a和b,先把深度大的节点提升到深度小的节点的相同深度,然后把a和b同时往上提,每次能提多少提多少,每次提了以后要保证节点a!=节点b,提升的高度从大往小找(先找n,再找n/2,再找n/4,再找n/8,再找n/16……最后再找1)。
而最后LCA就是a(或b)的父节点。

具体实现看代码吧……

4. 例题与代码

HDU – 2586 How far away ?传送门= ̄ω ̄=

思路:对于点a和点b,他们的树上距离是唯一的,也是最小的(因为树上任意两点直接只有一条通路),距离为a到根节点的距离+b到根节点的距离-2×(a和b的lca到根节点的距离)(很明显我就不证了^_^)。

注意!点到根节点的距离不同于点的深度!下面的代码中,deep[i]指节点i的深度,而far[i]表示节点i到根节点的距离!都通过递增得到!(根节点到根节点的距离为0,根节点的深度也为0)

代码:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxs=40005,logs=20;
int t,n,m,pre[maxs][logs+1],deep[maxs],far[maxs];
vector<int> g[maxs],dis[maxs];
void dfs(int x,int p)
{
    pre[x][0]=p;
    for(int i=1;i<=logs;i++)pre[x][i]=pre[pre[x][i-1]][i-1];
    for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)deep[g[x][i]]=deep[x]+1,far[g[x][i]]=far[x]+dis[x][i],dfs(g[x][i],x);
}
int getlca(int a,int b)
{
    if(deep[a]>deep[b])swap(a,b);
    for(int i=logs;i>=0;i--)if(deep[pre[b][i]]>=deep[a])b=pre[b][i];
    if(a==b)return a;
    for(int i=logs;i>=0;i--)if(pre[a][i]!=pre[b][i])a=pre[a][i],b=pre[b][i];
    return pre[a][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++){g[i].clear(),dis[i].clear();for(int j=0;j<=logs;j++)pre[i][j]=0;}
        for(int i=1,a,b,c;i<n;i++)cin>>a>>b>>c,g[a].push_back(b),g[b].push_back(a),dis[a].push_back(c),dis[b].push_back(c);
        dfs(1,0);
        for(int i=1,a,b;i<=m;i++)cin>>a>>b,cout<<far[a]+far[b]-2*far[getlca(a,b)]<<endl;
    }
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *