Subtask 1

• Test every possible $t$.

Subtask 2

• Sort the vertices by the distance from $s$. Then $t$ can be found using binary search.

Subtask 3

• Binary search.

Subtask 4

• One function call with weight of every edge $A$ to find the distance between $s$ and $t$ in unweighted $G$.
• An edge $e$ on the shortest path between $s$ and $t$ can be found using binary search.
• After removing $e$, the graph will be separated into two subtrees. Then you can perform the solution of Subtask 2 twice to find $s$ and $t$ separately.
• Centroid decomposition is possible but implementation will be tough.

Subtask 5

• Let $S$ be a subset of $V$, where $V$ is the set of vertices in $G$.
• We set the weight of edges between $S$ and $V\setminus S$ to $1$. The weights of other edges are set to $2$. Then, we can tell whether exactly one of $s$ and $t$ belongs to $S$ by looking at the parity of the answer to the call.
• Thus we can compute $s\text{xor}t$. Using this, we can also find $s$ and $t$ themselves.

Subtask 6

• Solution A: 21 points
  • A vertex $v$ on a shortest path between $s$ and $t$ can be found using binary search.
  • Construct a BFS tree with root $v$. Then, we can use binary search again to find one of $s$ and $t$.
  • The other can be found similarly.
• Solution B: 31 points
  • Find an edge $e$ on a shortest path between $s$ and $t$ as in Subtask 4.
  • Let $e=uv$. Without loss of generality, we can assume $s$, $u$, $v$ and $t$ appears in this order on this shortest path.
  • Then we can prove that $s$ is strictly closer to $u$ than to $v$. Similarly, $t$ is closer to $v$ than to $u$.
  • Thus we have disjoint candidate sets $S$ and $T$ such that $s$ and $t$ are contained in $S$ and $T$, respectively. At the same time, we can construct BFS trees of vertex sets $S$ and $T$ with roots $u$ and $v$, respectively. We can suppose a shortest path goes only through $e$ and edges in the BFS trees.
  • Now we can find $s$ and $t$ as in the last part of Subtask 4.