80pts求助
查看原帖
80pts求助
968912
ajsdlkasd楼主2023/7/20 11:20

#8#9TLE

import java.io.*;
import java.util.*;

public class Main{
    static int N = 500010,M = 2*N;
    static int[] h = new int[N],e = new int[M],ne = new int[M];
    static int[] depth = new int[N];
    static int[][] fa = new int[N][20];
    static int idx = 0,n,m,INF = 0x3f3f3f3f;
    static BufferedReader br
        = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer sc = new StreamTokenizer(br);
    static BufferedWriter bw
        = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws IOException{
        n = nextRead();
        m = nextRead();
        Arrays.fill(h,-1);
        for(int i = 1;i<=n-1;i++){
            int a = nextRead();
            int b = nextRead();
            add(a,b);
            add(b,a);
        }
        
        bfs();
        
        for(int i = 1;i<=m;i++){
            int a = nextRead(),
            b = nextRead(),
            c = nextRead();
            int lcaAB = lca(a,b),lcaAC = lca(a,c),
            lcaBC = lca(b,c);
            int ans = INF,node = -1;
            int x0 = dis(a,b)+dis(lcaAB,c);
            int x1 = dis(a,c)+dis(lcaAC,b);
            int x2 = dis(b,c)+dis(lcaBC,a);
            if(ans>x0){
                ans = x0;
                node = lcaAB;
            }
            if(ans>x1){
                ans = x1;
                node = lcaAC;
            }
            if(ans>x2){
                ans = x2;
                node = lcaBC;
            }
            bw.write(node+" "+ans+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    public static int dis(int a,int b){
        return depth[a]+depth[b]-2*depth[lca(a,b)];
    }
    public static int lca(int a,int b){
        if(depth[a]<depth[b]){
            int c = a;
            a = b;
            b = c;
        }
        for(int k = 19;k>=0;k--)
            if(depth[fa[a][k]]>=depth[b])
                a = fa[a][k];
                
        if(a == b) return a;
        for(int k = 19;k>=0;k--)
            if(fa[a][k]!=fa[b][k]){
                a = fa[a][k];
                b = fa[b][k];
            }
        return fa[a][0];
    }
    public static void bfs(){
        depth[0] = 0;
        depth[1] = 1;
        int[] q = new int[N];
        int hh = 0,tt = -1;
        q[++tt] = 1;
        while(tt>=hh){
            int t = q[hh++];
            for(int i = h[t];i!=-1;i = ne[i]){
                int j = e[i];
                if(depth[j] == 0){
                    depth[j] = depth[t]+1;
                    q[++tt] = j;
                    fa[j][0] = t;
                    for(int k = 1;k<=19;k++)
                        fa[j][k] = fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static int nextRead()throws IOException{
        sc.nextToken();
        return (int)sc.nval;
    }
}
2023/7/20 11:20
加载中...