## Closest Node to Path in Tree

• Time:O(n^2 + mn)
• Space:O(n^2)

## C++

``````class Solution {
public:
vector<int> closestNode(int n, vector<vector<int>>& edges,
vector<vector<int>>& query) {
vector<int> ans;
vector<vector<int>> graph(n);
vector<vector<int>> dist(n, vector<int>(n, -1));

for (const auto& e : edges) {
const int u = e[0];
const int v = e[1];
graph[u].push_back(v);
graph[v].push_back(u);
}

for (int i = 0; i < n; ++i)
fillDist(graph, i, i, 0, dist);

for (const auto& q : query) {
const int start = q[0];
const int end = q[1];
const int node = q[2];
ans.push_back(findClosest(graph, dist, start, end, node, start));
}

return ans;
}

private:
void fillDist(const vector<vector<int>>& graph, int start, int u, int d,
vector<vector<int>>& dist) {
dist[start][u] = d;
for (const int v : graph[u])
if (dist[start][v] == -1)
fillDist(graph, start, v, d + 1, dist);
}

int findClosest(const vector<vector<int>>& graph,
const vector<vector<int>>& dist, int u, int end, int node,
int ans) {
for (const int v : graph[u])
if (dist[v][end] < dist[u][end])
return findClosest(graph, dist, v, end, node,
dist[ans][node] < dist[v][node] ? ans : v);
return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] closestNode(int n, int[][] edges, int[][] query) {
int[] ans = new int[query.length];
List<Integer>[] graph = new List[n];
int[][] dist = new int[n][n];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, -1));

for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();

for (int[] e : edges) {
final int u = e[0];
final int v = e[1];
}

for (int i = 0; i < n; ++i)
fillDist(graph, i, i, 0, dist);

for (int i = 0; i < query.length; ++i) {
final int start = query[i][0];
final int end = query[i][1];
final int node = query[i][2];
ans[i] = findClosest(graph, dist, start, end, node, start);
}

return ans;
}

private void fillDist(List<Integer>[] graph, int start, int u, int d, int[][] dist) {
dist[start][u] = d;
for (final int v : graph[u])
if (dist[start][v] == -1)
fillDist(graph, start, v, d + 1, dist);
}

private int findClosest(List<Integer>[] graph, int[][] dist, int u, int end, int node, int ans) {
for (final int v : graph[u])
if (dist[v][end] < dist[u][end])
return findClosest(graph, dist, v, end, node, dist[ans][node] < dist[v][node] ? ans : v);
return ans;
}
}
``````

## Python

``````class Solution:
def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
ans = []
graph = [[] for _ in range(n)]
dist = [[-1] * n for _ in range(n)]

for u, v in edges:
graph[u].append(v)
graph[v].append(u)

def fillDist(start: int, u: int, d: int) -> None:
dist[start][u] = d
for v in graph[u]:
if dist[start][v] == -1:
fillDist(start, v, d + 1)

for i in range(n):
fillDist(i, i, 0)

def findClosest(u: int, end: int, node: int, ans: int) -> int:
for v in graph[u]:
if dist[v][end] < dist[u][end]:
return findClosest(v, end, node, ans if dist[ans][node] < dist[v][node] else v)
return ans

return [findClosest(start, end, node, start)
for start, end, node in query]
``````