n이 30000이나 될 수 있기 때문에 m번 최단거리를 BFS로 구하려면 n*O(n+m)이라 시간 초과고, 플로이드도 n이 너무 커서 사용할 수 없네요.

문제 조건에 이 그래프가 트리 형태라는 힌트(싸이클이 없다네요.)가 있는 걸로 보아, 제 생각엔 LCA(Least Common Ancestor) 문제로 보입니다.

발그림은 대단히 죄송하지만, 일단 이렇게 트리에서 두 정점이 주어지면 그 정점을 둘 다 자손 혹은 자신으로 하는 제일 깊은 깊이의 노드를 LCA, 최소 공통 조상이라고 합니다. 그림에서는 빨간 두 정점에 대한 LCA는 파란색으로 가리켜 놓았습니다. LCA는 루트일 수도, 아닐 수도 있으며 두 정점 중 하나일 수도 있습니다.

두 정점 u, v가 있을 때 트리상에서 u와 v 사이의 최단 거리는 u와 LCA 사이의 거리 + v와 LCA 사이의 거리입니다. 또한 두 정점 u, v가 주어지면 O(logn)의 시간에 LCA를 찾을 수 있는 알고리즘이 몇 가지 존재합니다.

따라서 방문 순서대로 최단거리를 저렇게 O(logn)만에 구해주시면 O(mlogn)으로 풀 수 있을 것 같네요.

아, 맨 위에 BFS 시간복잡도에 오류가 있네요. 저 문장을 쓸 당시 아무 생각없이 m을 간선 수라 생각했습니다. m*O(n)이라 보셔도 됩니다. 이것도 시간 초과입니다.

감사합니다! 다시 해볼게요

풀었습니다 감사합니다!

빠르시군요... 새벽에 서로 열심이네요. 축하드립니다!