算法分析

Tarjan – 离线求LCA
在线做法：读一个询问，处理一个，输出一个
离线做法：读完全部询问，再全部处理完，再全部输出

在深度优先遍历时，将所有点分成三大类

• 2号点：代表已经访问并结束回溯

• 1号点：代表正在访问

• 0号点：代表还没有访问过

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

• 1、先求出所有点到根结点的距离depth[]，设x号点和y号点的最近公共祖先是p,则x和y的最近距离等于depth[x] + depth[y] - 2 * depth[p]

• 2、在深度优先遍历1号点中的u点的时候，需要把u的查询的另外一个点的最短距离进行计算并存储，最后把u点合并到上一结点的集合

时间复杂度 $O(n + m)$

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main{
    static int N = 10010, M = N * 2;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static Map<Integer,List<Pair>> query = new HashMap<Integer,List<Pair>>();
    static int[] dist = new int[N];
    static int[] st = new int[N];
    static int[] p = new int[N];
    static int[] res = new int[M * 2];
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void dfs(int u,int father)
    {
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            dist[j] = dist[u] + 1;
            dfs(j,u);
        }
    }
    //所有节点分为三种状态
    //2 代表已经访问并结束回溯
    //1 代表正在访问
    //0 代表还没有访问到
    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;
            }
        }
        if(query.containsKey(u))
        {
            for(Pair pair : query.get(u))
            {
                int y = pair.first;
                int id = pair.id;
                //已经回溯结束
                if(st[y] == 2)
                {
                    int anc = find(y);
                    res[id] = dist[u] + dist[y] - dist[anc] * 2;
                }
            }
        }

        st[u] = 2;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();

        for(int i = 1;i <= n;i ++) p[i] = i;

        Arrays.fill(h, -1);
        for(int i = 0;i < n - 1;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            add(a,b,c);
            add(b,a,c);
        }
        for(int i = 0;i < m;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            if(a != b)
            {
                if(!query.containsKey(a)) query.put(a,new LinkedList<Pair>());
                query.get(a).add(new Pair(b,i));
                if(!query.containsKey(b)) query.put(b,new LinkedList<Pair>());
                query.get(b).add(new Pair(a,i));
            }
        }
        //计算每个点到根结点的距离
        dfs(1,-1);
        tarjan(1);

        for(int i = 0;i < m;i ++) System.out.println(res[i]);
    }
}
class Pair
{
    //first存查询的另外一个点，id存查询编号
    int first,id;
    Pair(int first,int id)
    {
        this.first = first;
        this.id = id;
    }
}