시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 16 | 10 | 10 | 66.667% |
간선의 가중치가 양수인 트리가 주어진다. 이때 트리란 사이클이 없는 무방향 연결그래프이다. 이 트리의 리프 노드들을 두개씩 묶어야 한다. 이때 묶는 비용은 묶여진 두 노드의 최단거리의 합이다. 만약 리프 노드의 개수가 홀수개라면 묶는 비용은 \(-1\) 이다. 이때 리프 노드란 연결된 간선의 개수가 \(1\)인 노드다. 쿼리가 주어진다. 각 쿼리는 \(x, w\)로 표현되며, 새로운 노드를 \(x\)에 붙이라는 의미이고 이때 새로운 간선의 가중치는 \(w\)다. 각 쿼리마다 쿼리 수행 후의 최소 묶는 비용을 구하여라. \(x\)는 트리에 있는 노드의 번호임이 보장되고, \(q\)번째 쿼리에서 생성된 새로운 노드의 번호는 \(n + q\) 이다. 노드번호는 \(1\)부터 시작한다
입력 첫줄에 트리의 처음 노드의 갯수가 주어지고, 다음줄부터 \(n-1\)개의 간선이 \(u, v, w\)순서대로 주어진다. 이는 \(u\)와 \(v\)가 가중치 \(w\)로 연결되어있다는 의미이다. 그 다음줄에 쿼리의 갯수 \(q\)가 주어지고 그 다음줄부터 쿼리 \(x, w\) 들이 주어진다. 이는 새로운 노드가 \(x\)하고 연결되고 이때 생기는 간선의 가중치가 \(w\)라는것을 의미한다.
각 쿼리마다 모든 리프를 묶는 최소 비용을 출력하라.
4 1 2 1 2 3 2 2 4 3 3 1 5 2 6 5 7
-1 17 24
8 8 6 3 5 6 1 1 8 4 3 8 1 7 5 5 2 3 9 4 3 2 7 5 6 6 5 2 3 3 5 4 8 5 9 8 7
-1 34 37 -1 -1 58 -1
University > 성균관대학교 > 2021 SKKU 프로그래밍 대회 in 소프트의 밤 E번