N 개의 고양이 타워가 있으며 각각 1에서 N까지 번호가 매겨져 있습니다. 타워 i (1≤i≤N)의 높이는 Pi입니다. 타워의 높이는 1 이상 N 이하의 다른 정수입니다. N-1 세트의 타워가 인접하고 각 j (1≤j≤N-1)에 대해 타워 Aj와 타워 Bj가 인접합니다. 우선, 어느 타워로부터 어느 타워에 인접하는 타워로 이동하는 조작을 반복해서 이동할 수 있다.

처음에는 고양이가 높이 N의 타워 위에 있습니다.

그런 다음 고양이 운동을 합니다. 고양이 운동은 하나의 타워를 선택하고 거기에 장애물을 놓는 조작의 반복입니다. 그러나 이미 장애물이 있는 타워에 장애물을 다시 놓을 수는 없습니다. 조작에 의해 다음이 일어난다.

• 선택한 타워에 고양이가 없으면 아무 일도 일어나지 않습니다.

• 선택한 타워에 고양이가 있고 인접한 모든 타워에 장애물이 있는 경우 고양이 운동이 종료됩니다.

• 어느 쪽도 아닌 경우, 장애물이 놓여 있지 않은 인접한 타워로의 이동을 반복하여 선택한 타워로부터 이동할 수 있는 타워 중, 선택한 타워를 제외하고 가장 높은 타워로, 인접하는 타워로의 이동을 반복하면 고양이가 움직입니다. 이 때 고양이는 인접한 타워로의 이동 횟수가 최소가 되도록 이동합니다.

타워 높이와 인접한 타워 세트의 정보가 주어졌을 때 장애물을 놓는 방법을 고안했을 때 고양이가 인접한 타워로 이동하는 횟수의 합계의 최대치를 구하는 프로그램을 작성하라.

#5834 upload 6 done 3 how_to_reg 3 call_split Subtask

고양이 운동 (Cat Exercise) timer 2s memory 1024MB

#5834
Subtask

고양이 운동 (Cat Exercise) 2s 1024MB