Courier Lulu

각 다리를 상자의 크기 $c$가 큰 순서대로 처리한다.

$dp[x]$를 지금까지 처리한, 즉 현재 다리보다 큰 크기의 상자만 사용해서 $x$번 섬에 도착했을 때 회수할 수 있는 상자 개수의 최댓값이라고 하자.

현재 처리하는 다리가 $u$와 $v$를 잇고 상자 크기가 $c$라고 하자. 이 다리를 마지막에 지나려면, 그 전에 회수한 모든 상자의 크기는 $c$보다 커야 한다. 그러므로 현재 다리를 지나기 전 상태는 이미 $dp$에 반영되어 있다.

가능한 전이는 두 가지이다.

• $u$번 섬에 도착해 있다가 이 다리를 지나 $v$번 섬으로 간다.
• $v$번 섬에 도착해 있다가 이 다리를 지나 $u$번 섬으로 간다.

따라서 다음과 같이 갱신한다.

$$\begin{aligned} dp[v] &\leftarrow \max(dp[v], dp[u] + 1),\\ dp[u] &\leftarrow \max(dp[u], dp[v] + 1). \end{aligned}$$

단, 같은 다리를 양방향으로 동시에 사용하는 것을 막기 위해 두 값은 갱신 전의 $dp[u]$, $dp[v]$를 저장해 둔 뒤 동시에 갱신해야 한다.

모든 상자의 크기가 서로 다르므로 같은 크기의 다리들을 따로 묶어 처리할 필요는 없다.

각 다리는 정확히 한 번 처리되고, 정렬에 $O(M \log M)$ 시간이 걸린다. 전체 시간 복잡도는 $O(M \log M)$, 메모리 복잡도는 $O(N+M)$이다.