最近公共祖先（Tarjin）

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

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

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

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

对于 $100\%$ 的数据，$1\le N,M\le 500000$，$1\le x,y,a,b\le N$，不保证 $a\ne 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];
    }
}

$Subtask\#0$ 过掉了，但是 $Subtask\#1$ $RE$ 了