N개의 노드 (10만)

M개의 쿼리 (10만)



viewimage.php?id=3dae&no=24b0d769e1d32ca73cef8efa11d028311f263ed599921c6ba339f17091436b660d243746a145954209e37acd504be94174e0fe8fc25c7214160afc8cfd

트리가 다음과 같이 주어질때

빠르게 노드간 거리를 탐색하는 방법이 있나요? 

N과 Q가 최대 10만이라 BFS나 DFS로 할 경우 시간초과가 나지 않나요?


입력 예:

5(노드 개수)  4(연결 노드) 4(쿼리 개수)

(연결 노드)

2 4 (4번의 부모노드 2)

1 5 (5번의 부모노드 1)

1 3 

1 2

(쿼리)

1 5 (1에서 5까지의 거리)  

2 3

3 5

1 4


출력:

2 (1 -> 5)

3 (2 -> 1 -> 3)

3 (3 -> 1 -> 5)

3 (1 -> 2 -> 4)