리프 매칭
시간 제한1초메모리 제한512 MB
가중치가 있는 트리에 질의마다 리프가 하나씩 추가될 때, 매번 모든 리프를 짝지었을 때의 최소 총 거리를 구하고 리프 수가 홀수이면 -1을 출력한다.
문제
간선의 가중치가 양수인 트리가 주어진다. 트리란 사이클이 없는 무방향 연결그래프이다. 이 트리의 리프 노드들을 두 개씩 묶어야 한다. 묶는 비용은 묶인 두 노드의 최단거리의 합이다. 리프 노드의 개수가 홀수라면 묶는 비용은 (-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)값의 노드는 존재한다.