시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB16101066.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\)라는것을 의미한다.

출력

각 쿼리마다 모든 리프를 묶는 최소 비용을 출력하라.

제한

  • \(3≤n≤10^5\)
  • \(1≤q≤10^5\)
  • \(1≤u,v≤n\)
  • \(1≤w≤10^9\)
  • 각 쿼리마다 주어지는 \(x\)값의 노드는 존재한다.

예제 입력 1

4
1 2 1
2 3 2
2 4 3
3
1 5
2 6
5 7

예제 출력 1

-1
17
24

예제 입력 2

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

예제 출력 2

-1
34
37
-1
-1
58
-1

출처

University > 성균관대학교 > 2021 SKKU 프로그래밍 대회 in 소프트의 밤 E번