小团无路可逃

//JS代码：基于dfs深度优先的回溯查找，根节点到目标节点的最长分支层数。
let info = readline().trim().split(' ').map(e=>parseInt(e))
//创建访问数组，记录节点的访问情况
let visited = Array(info[0]).fill(false)
let matrix = Array(info[0]).fill(0).map(e=>[])
//分别为最终耗时变量与根节点所在层数。
let time = 0 , rootc = 0
//循环读取输入，创建邻接表
for(let i = 0 ; i < info[0]-1 ; i++){
    let sideInfo = readline().trim().split(' ').map(e=>parseInt(e))
    matrix[sideInfo[0]-1].push(sideInfo[1]-1)
    matrix[sideInfo[1]-1].push(sideInfo[0]-1)
}
//带回溯的dfs将递归遍历出根节点（小美）到目标节点（小团）的最长分支层数
//v代表当前节点，pnode代表父节点；c代表当前层数，flag代表是否为小团所在树的分支。
function dfs(***ode,c = 0,flag = false){
//dfs的访问当前节点的操作区：
//当前节点为小团所在的初始节点时，flag置为true代表可访问该节点的子树，并递归传参。
    if(v === info[2]-1 ){
        flag = true
/*当前小团所在的节点与小美所在的节点层数中间隔有两层，则小团可向上（其父节点）走。此时目标节点为
其父节点。该单位时间小美也向下走一步，其rootc也加一。并重头递归再查找最大层数，并用return打断之后的递归*/
        if(c-rootc >= 3){
            info[2] = pnode + 1
            rootc++
            visited.fill(false)
            dfs(info[1]-1,0,0,false)
            return 0
        }
    } 
//如果当前节点是目标节点后代节点，并且为叶子节点，同时层数大于之前分支记录的叶子节点层数，则复制
    if(flag && matrix[v].length === 1 && c > time){
        time = c
    }
//dfs的基本遍历迭代操作区,访问完节点后，设置本节点已访问。层数加一，父节点置为当前节点。
    visited[v] = true
    c++
    pnode = v
//循环遍历出邻接表中当前节点在未访问节点为子节点，并递归以深度优先进行访问。
    for(let u of matrix[v]){
        if(!visited[u]){
            dfs(u,v,c,flag)
        }
    }
}
dfs(info[1]-1,0,0,false)
console.log(time)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        // 创建邻连接表（二叉树连接n-1<<n^2）
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) {tree.add(new ArrayList<>());}
        // 添加无向图的n-1条边
        for (int i = 0; i < n-1; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            tree.get(u).add(v);
            tree.get(v).add(u);
        }
        // 距离矩阵
        int[] dx = new int[n+1];
        int[] dy = new int[n+1];
        dfs(tree,dx,x,-1,0);
        dfs(tree,dy,y,-1,0);
        int out =0;
        for (int i = 1; i < n+1; i++) {
            if(dx[i]>dy[i])
                out = Math.max(out,dx[i]);
        }
        System.out.println(out);
    }
    public static void dfs(ArrayList<ArrayList<Integer>> tree,int[] ans,int start,int last,int step){
        for (int i : tree.get(start)){
            if(i==last)
                continue;
            ans[i]=step+1;
            dfs(tree,ans,i,start,step+1);
        }
    }
}

java：BFS+贪心

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int x = Integer.parseInt(params[1]);
        int y = Integer.parseInt(params[2]);
        // 邻接表建图
        Map<Integer,List<Integer>> edges = new HashMap<>();
        for(int i=1;i<n;++i){
            params = br.readLine().trim().split(" ");
            int p1 = Integer.parseInt(params[0]);
            int p2 = Integer.parseInt(params[1]);
            List<Integer> list1 = edges.getOrDefault(p1,new ArrayList<>());
            List<Integer> list2 = edges.getOrDefault(p2,new ArrayList<>());
            list1.add(p2);
            list2.add(p1);
            edges.put(p1,list1);
            edges.put(p2,list2);
        }
        // x,y到其他节点的距离
        int[] disX = new int[n+1];
        int[] disY = new int[n+1];
        getDistance(disX,edges,x);
        getDistance(disY,edges,y);
        // 小美可能在任何节点抓到小团，定义那个节点为终点
        // 1.要使时间最大，则小美到终点的距离一定 > 小团到终点的距离。因为两个人都要走到终点，所以小美到终点走过的路径会包含小团的
        // 所以最大值就是满足条件1下的小美到终点的最大值
        int maxTime = Integer.MIN_VALUE;
        for(int i=1;i<=n;++i){
            if(disX[i] > disY[i]){
                maxTime = Math.max(maxTime,disX[i]);
            }
        }
        System.out.println(maxTime);
    }

    // 求节点start到其他节点的距离
    public static void getDistance(int[] dis,Map<Integer,List<Integer>> edges,int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        // 记录节点是否被访问过
        boolean[] visited = new boolean[dis.length];
        visited[start] = true;
        while(!queue.isEmpty()){
            // 当前节点
            int curNode = queue.poll();
            // 遍历与当前节点直接相连的节点
            for(int nextNode:edges.get(curNode)){
                if(!visited[nextNode]){
                    // start到下一个节点的距离 = start到当前节点的距离 + 1；
                    dis[nextNode] = dis[curNode] + 1;
                    queue.offer(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}

这道题本质上是找出，满足X到这个点的距离小于Y到这个点的距离，然后取最大的disX,这么做的前提是这是一棵树，及只有任意两点之间只有一条通路，所以只要dis(x, i) > dis(y, i), 就不会在路径中某处相遇，具体步骤分以下几步：
1. 建立邻接表
2. BFS计算x/y到其他点的距离
3. 找出满足条件的最大disX

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        if (x == y) {
            System.out.print(0);
            return;
        }
        // build neighbor table
        Node[] nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int p1 = in.nextInt();
            int p2 = in.nextInt();
            nodes[p1].neighbor.add(nodes[p2]);
            nodes[p2].neighbor.add(nodes[p1]);
        }
        // calculate distance for x/y to other node
        int[] disX = findDistance(nodes, n, x);
        int[] disY = findDistance(nodes, n, y);
        // find the res
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (disY[i] < disX[i]) {
                res = Math.max(res, disX[i]);
            }
        }
        System.out.println(res);
    }
    
    /* BFS */
    static int[] findDistance(Node[] nodes, int n, int pos) {
        int[] dis = new int[n + 1];
        Arrays.fill(dis, -1);
        LinkedList<Node> queue = new LinkedList<Node>();
        dis[pos] = 0;
        queue.offer(nodes[pos]);
        int distance = 1;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node current = queue.poll();
                for (Node node : current.neighbor) {
                    if (dis[node.val] == -1) {
                        dis[node.val] = distance;
                        queue.offer(node);
                    }
                }
            }
            distance++;
        }
        return dis;
    }
    
    static class Node {
        int val;
        ArrayList<Node> neighbor;
        public Node(int val) {
            this.val = val;
            neighbor = new ArrayList<Node>();
        }
    }
}

// BFS 统计 A 和 B 到所有点的最短路, 结果取 B 先到 A 后到的最大路径即可
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>

using namespace std;
using PII = pair<int, int>;

const int N = 50010;
int h[N], e[N], ne[N], idx;
vector<int> dist_x, dist_y;
int n, x, y;
vector<vector<int>> path;
//vector<PII> x_dis, y_dis;

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

void bfs(int u, vector<int>& dist){
    dist = vector<int>(n + 1, -1);
    queue<int> q;
    q.push(u);
    dist[u] = 0;
    // if(flag == 0) x_dis.push_back({u, dist[u]});
    // else y_dis.push_back({u, dist[u]});

    while(q.size()){
        auto t = q.front(); q.pop();
        for(auto j : path[t]){
            if(dist[j] == -1){
                dist[j] = dist[t] + 1;
                q.push(j);
                // if(flag == 0) x_dis.push_back({j, dist[j]});
                // else y_dis.push_back({j, dist[j]});
            }
        }
    }
}

int main()
{
    cin >> n >> x >> y;
    memset(h, -1, sizeof(h));
    path.resize(n + 1);

    for(int i = 0; i < n; ++i){
        int a, b;
        cin >> a >> b;
        // add(a, b), add(b, a);
        path[a].push_back(b);
        path[b].push_back(a);
    }

    bfs(x, dist_x);
    bfs(y, dist_y);

    // sort(x_dis.begin(), x_dis.end());
    // sort(y_dis.begin(), y_dis.end());

    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(dist_y[i] < dist_x[i]) ans = max(ans, dist_x[i]);
    }
    cout << ans << endl;

    return 0;
}

    #include <unordered_map>
    #include <vector>
    #include <iostream>
    using namespace std;
    unordered_map<int,vector<int>> umap;
    void dfs(int m, int n, vector<int> &trace){ //参数1表示起始结点 参数2表示可达结点 参数3记录从起始结点到当前结点的最短路径
        trace[m] = trace[n] + 1; //起始结点即结点本身，距离为0
        int len = umap[m].size(); //记录起始结点的周围结点
        for(int i = 0; i < len; i++){
            int l = umap[m][i]; //结点z即起始结点的其中一个周围结点
            if(l == n) continue;
            // trace[1] = 1;
            // trace[3] = 2;
            // trace[5] = 3;
            // trace[4] = 1;
            dfs(l,m,trace); //以结点2为起始结点，结点1与结点4为周围结点，从起始结点2到结点4的最短路径为1 dfs(4,2,trace) break
            //从起始结点2到结点1的最短路径为1 dfs(1,2,trace)=1 dfs(3,2,trace)=2 dfs(5,2,trace)=3
        }
    }
    int main(){
        int n,x,y; //树上结点数量 小美->小团所在位置(1~n)
        cin>>n>>x>>y;

        for(int i = 0; i < n - 1; i++){ //umap[i]保存树上某一个结点[i]的周围结点vector<int>
            int u,v;
            cin>>u>>v;
            umap[u].push_back(v);
            umap[v].push_back(u);
        }
        int ret = 0;
        vector<int> trace_x(n+1); //结点x到达其余所有结点的最短路径[0]=-1
        vector<int> trace_y(n+1); //结点y到达其余所有结点的最短路径[0]=-1
        trace_x[0] = trace_y[0] = -1;
        dfs(x,0,trace_x);
        //for(int i = 0; i <= n; i++){
        //    cout<<trace_x[i]<<" ";
        //}
        //cout<<endl; //-1 0 1 1 2 2
        dfs(y,0,trace_y);
        //for(int i = 0; i <= n; i++){
        //    cout<<trace_y[i]<<" ";
        //} //-1 1 0 2 1 3

        for(int i = 1; i <= n; i++){ //i=1~n
            if(trace_y[i] < trace_x[i]){ //当结点y到达的某一个结点比结点x快时，才符合小美追逐小团的条件
                ret = max(ret, trace_x[i]);
            }
        }
        cout<<ret;
        return 0;
    }

import java.awt.Point;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        List<Integer>[] graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++)
            graph[i] = new ArrayList<>();
        boolean[] vis = new boolean[n+1];
        for(int i=1;i<n;i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        if(x==y){
            System.out.println(0);
            return;
        }

        int[] distanceToX = new int[n+1];
        int[] distanceToY = new int[n+1];
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,0));
        while(!queue.isEmpty()){
            Point point = queue.poll();
            int next = point.x;
            int distance = point.y;
            for(int j:graph[next]){
                if(!vis[j]){
                    distanceToX[j] = distance+1;
                    queue.offer(new Point(j,distance+1));
                    vis[j] = true;
                }
            }
        }
        Arrays.fill(vis,false);
        queue.offer(new Point(y,0));
        while(!queue.isEmpty()){
            Point point = queue.poll();
            int next = point.x;
            int distance = point.y;
            for(int j:graph[next]){
                if(!vis[j]){
                    distanceToY[j] = distance+1;
                    queue.offer(new Point(j,distance+1));
                    vis[j] = true;
                }
            }
        }
        //System.out.println(Arrays.toString(distanceToX));
        //System.out.println(Arrays.toString(distanceToY));
        int max = 0;
        for(int i=1;i<=n;i++){
            if(distanceToX[i]>distanceToY[i])
                max = Math.max(max,distanceToX[i]);
        }
        System.out.println(max);
    }
}