Closest Node to Path in Tree

Statement

You are given a positive integer, n, representing the number of nodes in a tree, numbered from $0$ to $n-1$. You are also given a 2D integer array edges of length $n-1$, where edges[i] $= [u_i, v_i]$ indicates that there is a bidirectional edge connecting nodes $u_i$ and $v_i$.

You are also given a 2D integer array query of length $m$, where query[i] $= [start_i, end_i, node_i]$.

For each query i, find the node on the path between $start_i$ and $end_i$ that is closest to $node_i$ in terms of the number of edges.

Return an integer array where the value at index $i$ corresponds to the answer for the $i^{th}$ query.

Note: If there are multiple such nodes at the same minimum distance, return the one with the smallest index.

Constraints:

• $1 \leq$ n $\leq 1000$

• edges.length $== n - 1$

• edges[i].length $== 2$

• $0 \leq u_i, v_i \leq n-1$

• $u_i \space != v_i$

• $1 \leq$ query.length $\leq 1000$

• query[i].length $== 3$

• $0 \leq start_i, end_i, node_i \leq n-1$

• The graph is a tree.

Examples