跳到主要内容

最近公共祖先

AcWing 1172. 祖孙询问​

题目​

https://www.acwing.com/problem/content/1174/ 给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。 有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

思路​

LCA倍增算法模板题目。

代码​

#include <bits/stdc++.h>

using namespace std;

const int N=40010,M=N*2;

int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][16];
int q[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    int hh=0,tt=0;
    q[0]=root;
    while (hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[++tt]=j;
                fa[j][0]=t;
                for(int k=1;k<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    if (depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
        if (depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if (a==b) return a;
    for(int k=15;k>=0;k--)
        if (fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}

int main() {
    cin>>n;
    int root=0;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if (b==-1) root=a;
        else add(a,b),add(b,a);
    }
    bfs(root);
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        int p= lca(a,b);
        if (p==a) cout<<"1"<<endl;
        else if (p==b) cout<<"2"<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

AcWing 1171. 距离​

题目​

https://www.acwing.com/problem/content/1173/ 给出 n 个点的一棵树，多次询问两点之间的最短距离。 注意：边是无向的。 所有节点的编号是 1,2,…,n。

思路​

Tarjan离线做法，先读完全部询问，然后全部处理完，最后再全部输出 在深度优先遍历时，将所有点分成三大类

  • 2号点：代表已经访问并结束回溯
  • 1号点：代表正在访问
  • 0号点：代表还没有访问过

其中所有2号点和正在搜索的1号点路径中已经通过并查集合并成一个集合

  1. 先求出所有点到根结点的距离depth[]，设x号点和y号点的最近公共祖先是p,则x和y的最近距离等于depth[x] + depth[y] - 2 * depth[p]
  2. 在深度优先遍历1号点中的u点的时候，需要把u的查询的另外一个点的最短距离进行计算并存储，最后把u点合并到上一结点的集合

代码​

#include <bits/stdc++.h>

using namespace std;
typedef  pair<int,int> PII;
const int N=10010,M=N*2;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];//first存查询的另外一个点，second存查询编号

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    if (p[x]!=x) p[x]= find(p[x]);
    return p[x];
}
void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if (j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(PII item:query[u])
    {
        int y=item.first,id=item.second;
        if (st[y]==2)
        {
            int anc=find(y);
            res[id]=dist[u]+dist[y]-dist[anc]*2;
        }
    }
    st[u]=2;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if (a!=b)
        {
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    
    for(int i=1;i<=n;i++) p[i]=i;
    dfs(1,-1);
    tarjan(1);
    for(int i=0;i<m;i++) cout<<res[i]<<endl;
    return 0;
}
0%