34258번 - 레몬향의 마흐트 서브태스크언어 제한함수 구현

레몬향의 마흐트, 뎅켄의 스승이자 칠붕현 중 한 명. 그는 모든 것을 레몬으로 바꾸는 마법으로 유명하다.

대마법사 프리렌은 레몬으로 변해 버린 뎅켄의 고향을 원래대로 되돌리기 위해, 마흐트의 마법을 해주(解呪)해야 한다.

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

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

마력 조작

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

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

이때 정점 $i$에 흐르는 마력 $f(i)$는 다음과 같이 계산된다.

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

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

조작이 끝난 후 프리렌은 루트 정점 $0$에 흐르는 마력 $f(0)$만을 알 수 있다. 또한 각 마력 조작은 서로 독립적으로 수행되며, 조작이 끝나면 마법진은 즉시 원상태로 복구된다.

프리렌을 도와 마흐트의 마법을 해주하기 위해, 모든 간선 중 용량의 최솟값을 찾아라.

함수 구현에 앞서 #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);

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

• $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$.

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

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

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

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

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

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

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는 다음을 출력한다.

$queries\_cnt$

$min\_W$

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

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

• macht.zip