동적 별 확장 그래프의 전역 최소 컷

$N$개의 정점과 $M$개의 간선으로 이루어진 단순 가중 무방향 그래프 $G$가 주어진다. $i$번째 간선은 $\lbrace u_i, v_i \rbrace$이며 가중치는 $w_i$이다.

$G$에 새로운 정점 $N$과 새로운 간선 $N$개를 추가하여 얻은 그래프를 $H$라고 하자. $i$번째 간선은 $\lbrace i, N \rbrace$이며 가중치는 $a_i$이다.

다음 $Q$개의 쿼리를 순서대로 처리한다.

• 간선 $\lbrace x_i,N \rbrace$의 가중치를 $y_i$로 변경하고, $H$의 전역 최소 컷 크기를 출력한다.

제약 조건

• $1 \le N \le 4000$
• $0 \le M \le \min ( \frac{N(N-1)}{2} , 4000 )$
• $1 \le Q \le 200000$
• $0 \le a_i \le 1000000000$
• $0 \le u_i, v_i \lt N$
• $u_i \neq v_i$
• $\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$
• $0 \le w_i \le 1000000000$
• $0 \le x_i \lt N$
• $0 \le y_i \le 1000000000$

$N$ $M$ $Q$
$a_0$ $a_1$ $\ldots$ $a_{N-1}$
$u_0$ $v_0$ $w_0$
$u_1$ $v_1$ $w_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$ $w_{M-1}$
$x_0$ $y_0$
$x_1$ $y_1$
$\vdots$
$x_{Q-1}$ $y_{Q-1}$

간선 $\lbrace x_i,N \rbrace$의 가중치를 $y_i$로 변경하고, $H$의 전역 최소 컷 크기를 출력한다.