# 2277. Closest Node to Path in Tree
###### tags: `Leetcode` `Hard` `DFS` `BFS`
Link: https://leetcode.com/problems/closest-node-to-path-in-tree/description/
## 思路
先把每个点当起点 算每两个点之间的最短路径
然后对于每个query做dfs, 对于能够通往end的这个分支上的节点, 取dist最小的node
## Code

class Solution {
    int minNode;
    public int[] closestNode(int n, int[][] edges, int[][] query) {
        int[][] dist = new int[n][n];
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        for(int i=0; i<n; i++){
            Queue<Integer> q = new LinkedList<>();
            boolean[] visited = new boolean[n];
            q.add(i);
            visited[i] = true;
            int d = 0;
            while(!q.isEmpty()){
                int size = q.size();
                for(int j=0; j<size; j++){
                    int curr = q.poll();
                    dist[i][curr] = d;
                    for(int next:graph.get(curr)){
                        if(!visited[next]){
                            visited[next] = true;
                            q.add(next);
                        }
                    }
                }
                d++;
            }
        }
        int[] ans = new int[query.length];
        for(int i=0; i<query.length; i++){
            int[] q = query[i];
            int s = q[0], e = q[1], node = q[2];
            minNode = s;
            boolean[] visited = new boolean[n];
            visited[s] = true;
            dfs(s, e, node, graph, dist, visited);
            ans[i] = minNode;
        }
        return ans;
    }
    private boolean dfs(int s, int e, int node, List<List<Integer>> graph, int[][] dist, boolean[] visited){
        if(s==e) return true;
        for(int next:graph.get(s)){
            if(visited[next]) continue;
            visited[next] = true;
            if(dfs(next, e, node, graph, dist, visited)){
                if(dist[minNode][node]>dist[next][node]){
                    minNode = next;
                }
                return true;
            }
        }
        return false;
    }
}