#11 레몬향의 마흐트

Statement

레몬향의 마흐트, 뎅켄의 스승이자 칠붕현 중 한 명. 그는 모든 것을 레몬으로 바꾸는 마법으로 유명하다. 대마법사 프리렌은 레몬으로 변해 버린 뎅켄의 고향을 원래대로 되돌리기 위해, 마흐트의 마법을 해주(解呪)해야 한다.

마흐트의 마법진은 $0,1,\dots,N-1$ 번까지 번호가 붙은 $N$ 개의 정점으로 이루어져 있고 루트가 $0$ 인 트리의 형태이다. 각 간선은 자식에서 부모로 향하는 유향 간선이다. $i$ 번째 간선은 $V[i]$ 번 정점에서 $U[i]$ 번 정점으로 향하는 방향의 용량 $W[i]$ 를 갖는 간선이다.

프리렌이 해주를 성공시키기 위해서는 모든 간선 중 최소 용량을 찾아야 한다. 즉, $W[i]$ 의 최솟값을 구해야 한다. 하지만 프리렌은 $N$ , $U[i]$ , $V[i]$ 만 알 뿐, $W[i]$ 는 알지 못한다. 따라서 그녀는 마력 조작을 통해 정보를 얻어야 한다.

프리렌은 최대 $200$ 번까지 마력 조작을 할 수 있으며, 한 번의 조작은 다음과 같이 이루어진다.

몇몇 간선을 선택하여 그 용량 $W[i]$ 를 $10^{10}$ 으로 강화한다.
각 정점에 흘려보낼 마력량을 정한다. 즉, 길이 $N$ 의 배열 $(F[0], F[1], \dots, F[N-1])$ 을 정의하고, $i$ 번 정점에 $F[i]$ 만큼의 마력을 흘려보낸다. 이때 정점 $i$ 에 흐르는 마력 $f(i)$ 는 다음과 같이 계산된다.

$f(i) = F[i] + \displaystyle\sum_{j \to i} \min \bigl(W,\, f(j)\bigr)$

여기서 $j \to i$ 는 $j$ 에서 $i$ 로 향하는 간선을 의미하고, $W$ 는 그 간선의 용량이다.

조작이 끝난 후 프리렌은 루트 정점 $0$ 에 흐르는 마력 $f(0)$ 만을 알 수 있다. 또한 각 마력 조작은 서로 독립적으로 수행되며, 조작이 끝나면 마법진은 즉시 원상태로 복구된다. 프리렌을 도와 마흐트의 마법을 해주하기 위해, 모든 간선 중 용량의 최솟값을 찾아라.

Implementation Details

함수 구현에 앞서 #include "macht.h" 를 통해 "macht.h" 헤더 파일을 포함해야 한다.

당신은 다음 함수를 구현해야 한다.

void unravel(std::vector<int> U, std::vector<int> V)

$U, V$ : 마법진의 간선을 나타내는 길이 $N-1$ 의 배열
이 함수는 하나의 테스트 케이스에 대해 단 한 번만 호출된다.
이 함수 안에서 아래 trigger 함수를 이용해 마력 조작을 할 수 있다.

long long trigger(std::vector<int> R, std::vector<int> F);

$R$ : 각 간선의 강화 여부를 의미하는 길이 $N-1$ 의 배열 ( $0\le R[i] \le 1$ )
$R[i] = 1$ 이면 $i$ 번 간선을 강화한다.
$F$ : 각 정점에 흘릴 마력량을 의미하는 길이 $N$ 의 배열 ( $0 \le F[i] \le 100\ 000$ )
이 함수는 루트 정점 $0$ 에 흐르는 마력량 $f(0)$ 을 반환한다.
만약 위 조건을 어기면 $-1$ 을 반환한다.
이 함수는 최대 $200$ 회 호출할 수 있다.
최종적으로, 해답을 제출하기 위해 아래 함수를 호출해야 한다.

void answer(int min_W);

$\text{min\_W}$ : 최소 용량의 값 (즉, $\min W[i]$ ) ( $1 \leq \text{min\_W} \leq 10^5$ )
단 한 번만 호출해야 한다.

Constraints

$2 \le N \le 50\ 000$ .
$0 \le U[i] < V[i] \le N-1$ ( $0 \le i \le N-2$ ).
$1 \le W[i] \le 100\ 000$ .

Subtasks

#	점수	제한
1	10	$U[i] = i, \ V[i] = i+1$ ( $0 \leq i \leq N - 2$ ).
2	17	$N \leq 3 \ 000$ , $U[i] = \left\lfloor \displaystyle\frac{i}{2} \right\rfloor, \ V[i] = i+1$ ( $0 \leq i \leq N - 2$ ).
3	21	$U[i] = 0, \ V[i] = i+1$ ( $0 \leq i \leq N - 2$ ).
4	42	$N \le 3\ 000$ .
5	10	추가적인 제약 조건이 없다.

Samples

다음과 같은 호출을 생각하자.

unravel(3, [0, 0], [1, 2])

다음은 가능한 함수 호출 순서 중 하나이다.

함수 호출	반환값
`trigger([0, 0], [3, 2, 1])`
	$6$
`trigger([1, 0], [0, 0, 2])`
	$1$
`answer(1)`

두 번째 trigger 호출 결과로부터, $1$ 번 간선 (정점 $0$ 과 $2$ 를 잇는 간선)의 가중치가 정확히 $1$ 임을 알 수 있다.

또한 첫 번째 trigger 호출 결과와 이 정보를 조합하면, $0$ 번 간선 (정점 $0$ 과 $1$ 를 잇는 간선)의 가중치는 $2$ 이상이어야 함을 알 수 있다. 만약 그렇지 않았다면, 루트에 흐르는 마력의 값은 $6$ 보다 작게 나왔을 것이다.

따라서 모든 간선 가운데 최소 용량은 $1$ 임을 확정할 수 있다.

Sample Grader

Sample grader의 입력 형식은 아래와 같다.

$N$ $U[0] \ V[0] \ W[0]$ $U[1] \ V[1] \ W[1]$ $\vdots$ $U[N-2] \ V[N-2] \ W[N-2]$

Sample grader는 다음을 출력한다.

$\text{queries\_cnt}$ $\text{min\_W}$

$\text{queries\_cnt}$ : trigger 함수가 호출된 횟수
$\text{min\_W}$ : answer 함수로 제출한 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

레몬향의 마흐트