最近公共祖先（Tarjin）

【模板】最近公共祖先（LCA）

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的数据， $N\leq 10$ ， $M\leq 10$ 。

对于 $70\%$ 的数据， $N\leq 10000$ ， $M\leq 10000$ 。

对于 $100\%$ 的数据， $\leq N,M\leq 500000$ ， $\leq x, y,a ,b \leq N$ ，不保证 $\neq b$ 。

样例说明：

该树结构如下：

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

第二次询问： $3, 2$ 的最近公共祖先，故为 $4$ 。

第三次询问： $3, 5$ 的最近公共祖先，故为 $1$ 。

第四次询问： $1, 2$ 的最近公共祖先，故为 $4$ 。

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

故输出依次为 $4, 4, 1, 4, 4$ 。

Java代码

import java.util.*;
import java.io.*;
class Point
{
    int y;
    int id;
    public Point(){}
    public Point(int y,int id)
    {
        this.y=y;
        this.id=id;
    }
}
public class Main
{
    public static int N=500010;
    public static int M=2*N;
    public static int n,m,s,idx;
    public static int[] h = new int[N];
    public static int[] e = new int[M];
    public static int[] ne = new int[M];
    public static int[] dist = new int[N];
    public static int[] p = new int[N];  //并查集
    public static int[] res = new int[N];
    public static int[] st = new int[N];
    public static ArrayList<ArrayList<Point>> query = new ArrayList<>();  //存询问
    public static void main(String[] args) throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        in.nextToken();
        m=(int)in.nval;
        in.nextToken();
        s=(int)in.nval;
        Arrays.fill(h,-1);
        for(int i=0;i<=n;i++)
            query.add(new ArrayList<>());
        for(int i=0;i<n-1;i++)  //建立边
        {
            in.nextToken();
            int a=(int)in.nval;
            in.nextToken();
            int b=(int)in.nval;
            add(a,b);
            add(b,a);
        }
        
        for(int i=0;i<m;i++)  //m组询问
        {
            in.nextToken();
            int a=(int)in.nval;
            in.nextToken();
            int b=(int)in.nval;
            if(a != b)
            {
                query.get(a).add(new Point(b,i));
                query.get(b).add(new Point(a,i));
            }
        }
        
        for(int i=1;i<=n;i++)  //初始化并查集
            p[i]=i;
            
        tarjan(s);
        
        for(int i=0;i<m;i++)
            out.println(res[i]);
            
        out.flush();
    }
    public static void add(int a,int b)
    {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static void tarjan(int u)
    {
        st[u]=1;  //正在遍历
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(st[j]==0)
            {
                tarjan(j);
                p[j]=u;
            }
        }
        
        //此时已到叶节点
        for(Point point : query.get(u))
        {
            int y=point.y;
            int id=point.id;
            
            if(res[id]!=0)  continue;  //如果已经回答过
            
            if(st[y]==2)  //如果已经回溯过
                res[id]=find(y);
        }
        
        st[u]=2;
    }
    public static int find(int x)
    {
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
}