정점 사이의 거리
시간 제한2초메모리 제한128 MB
최대 40,000개 정점을 가진 가중치 트리에서 최대 10,000개의 질의에 대해 두 정점 간 경로 거리를 LCA 기반 방법으로 구하는 문제입니다.
문제
N개의 정점으로 이루어진 가중치가 있는 트리가 주어진다. 이어서 M개의 정점 쌍이 주어질 때, 각 쌍에 대해 두 정점 사이의 경로 길이를 출력하라.
- 2 <= N <= 40,000
- 1 <= M <= 10,000
입력
첫째 줄에 정점의 개수 N이 주어진다. 다음 N - 1개의 줄에는 트리에서 연결된 두 정점과 그 간선의 거리가 주어진다.
그다음 줄에 질의의 개수 M이 주어진다. 다음 M개의 줄에는 거리를 알고 싶은 두 정점이 한 줄에 하나의 쌍씩 주어진다.
정점 번호는 1번부터 N번까지이다. 각 간선의 거리는 10,000 이하의 자연수이다.
출력
입력된 M개의 질의 순서대로, 각 줄에 해당 두 정점 사이의 거리를 출력한다.