6170 : 가상 트리 (Auxiliary Tree)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치가 있는 트리에서 쿼리마다 핵심 노드들의 집합이 주어집니다. 이 핵심 노드들과 그 조상 노드들로만 구성된 가상 트리(Auxiliary Tree)의 모든 간선의 가중치 합을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v, w가 주어집니다.
그 다음 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 50,000)가 주어집니다.
이어지는 Q개의 줄에 핵심 노드의 개수 K와 K개의 핵심 노드 번호가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v, w가 주어집니다.
그 다음 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 50,000)가 주어집니다.
이어지는 Q개의 줄에 핵심 노드의 개수 K와 K개의 핵심 노드 번호가 공백으로 구분되어 주어집니다.
출력 설명
각 쿼리마다 가상 트리의 간선 가중치 합을 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2 5
1 3 2
3 4 8
3 5 3
2
3 4 5 2
2 1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
18
10