시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 2 1 1 100.000%

문제

수라바야 시는 N개의 분기점이 있는데, 0부터 $N - 1$로 번호가 매겨져 있다. 이 분기점들은 $N - 1$개의 양방향 도로로 연결되어 있고, 0부터 $N - 2$로 번호가 매겨져 있다. 서로 다른 두 분기점을 어떻게 고르더라도 이 둘을 잇는 유일한 경로가 있다. 도로 $i$ ($0 \le i \le N - 2$)는 분기점 $U[i]$와 $V[i]$를 연결한다.

환경 문제에 대한 경각심을 높이기 위해서 수라바야 시의 시장 김 박사는 자동차 없는 날을 지정하려고 한다. 자동차 없는 날 행사로, 김 박사는 도로를 폐쇄하려고 한다. 폐쇄할 도로는 다음과 같이 정해진다. 김 박사는 먼저 음이 아닌 정수 $k$를 고르고, 모든 분기점에 $k$개 이하의 폐쇄되지 않은 도로가 직접 연결되어 있도록 한다. 도로 $i$를 폐쇄하는 비용은 $W[i]$이다.

김 박사를 도와서 가능한 음이 아닌 정수 $k$ ($0 \le k \le N - 1$) 각각에 대해 조건을 만족하게 도로를 폐쇄하는 최소 비용을 구하자.

구현

다음 함수를 구현해야 한다.

int64[] minimum_closure_costs(int N, int[] U, int[] V, int[] W)
  • $N$: 수라바야의 분기점 수
  • $U$, $V$ : 길이 $N - 1$인 배열로, 분기점 $U[i]$와 $V[i]$는 도로 $i$로 연결되어 있다.
  • $W$: 길이 $N - 1$인 배열로, $W[i]$는 도로 $i$를 폐쇄하는데 드는 비용이다.
  • 이 함수는 하나의 배열 $N$을 리턴해야 한다. 각각 $k$마다 ($0 \le k \le N - 1$), 이 배열의 $k$번째 원소는 모든 분기점이 직접 연결된 폐쇄되지 않은 도로가 최대 $k$개가 되도록 도로를 폐쇄하는 최소 비용이다.
  • 이 함수는 정확하게 한 번 호출된다.

예제 1

다음 호출을 생각해보자.

minimum_closure_costs(5, [0, 0, 0, 2], [1, 2, 3, 4], [1, 4, 3, 2])

이는 총 5개의 분기점이 있고, 이를 잇는 도로 4개가 (0, 1), (0, 2), (0, 3), (2, 4)을 잇고, 이 도로를 폐쇄하는 비용은 각각 1, 4, 3, 2라는 뜻이다.

최소 비용을 구하기 위해서는 다음과 같다.

  • 김 박사가 $k = 0$으로 고르면, 모든 도로가 폐쇄되어야 하므로 총 비용은 1 + 4 + 3 + 2 = 10이다.
  • 김 박사가 $k = 1$로 고르면, 도로 0과 도로 1을 폐쇄하면 총 비용 1 + 4 = 5가 된다.
  • 김 박사가 $k = 2$로 고르면, 도로 0을 폐쇄하면 총 비용 1이 된다.
  • 김 박사가 $k = 3$ 또는 $k = 4$를 고르면, 어느 도로도 폐쇄하지 않아도 된다.

따라서, minimum_closure_costs의 리턴값은 [10, 5, 1, 0, 0]이다.

예제 2

다음 호출을 생각해 보자.

minimum_closure_costs(4, [0, 2, 0], [1, 0, 3], [5, 10, 5])

이는 총 4개의 분기점이 있고, 이를 잇는 도로 3개가 (0, 1), (2, 0), (0, 3)을 잇고, 이 도로를 폐쇄하는 비용은 각각 5, 10, 5라는 뜻이다.

최소 비용을 구하기 위해서는 다음과 같다.

  • 김 박사가 $k = 0$으로 고르면, 모든 도로가 폐쇄되어야 하므로 총 비용은 5 + 10 + 5 = 20이다.
  • 김 박사가 $k = 1$로 고르면, 도로 0과 도로 2을 폐쇄하면 총 비용 5 + 5 = 10이 된다.
  • 김 박사가 $k = 2$로 고르면, 도로 0 또는 도로 2을 폐쇄하면 총 비용 5가 된다.
  • 김 박사가 $k = 3$을 고르면, 어느 도로도 폐쇄하지 않아도 된다.

따라서, minimum_closure_costs의 리턴값은 [20, 10, 5, 0]이다.

제한

  • $2 \le N \le 100\,000$
  • $0 \le U[i], V[i] \le N - 1$ (모든 $0 \le i \le N - 2$)
  • 어떤 두 분기점도 하나 또는 그 이상의 도로를 통해서 연결되어 있다.
  • $1 \le W[i] \le 10^9$ (모든 $0 \le i \le N - 2$)

서브태스크

번호 배점 제한
1 5

$U[i] = 0$ (모든 $0 \le i \le N - 2$)

2 7

$U[i] = i$, $V[i] = i + 1$ (모든 $0 \le i \le N - 2$)

3 14

$N \le 200$

4 10

$N \le 2000$

5 17

$W[i] = 1$ (모든 $0 \le i \le N - 2$)

6 25

$W[i] \le 10$ (모든 $0 \le i \le N - 2$)

7 22

추가적인 제약 조건이 없다.

W3sicHJvYmxlbV9pZCI6IjIxODUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHViODVjIFx1ZDNkMFx1YzFjNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjE4XHViNzdjXHViYzE0XHVjNTdjIFx1YzJkY1x1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YmQ4NFx1YWUzMFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIDBcdWJkODBcdWQxMzAgJE4gLSAxJFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmQ4NFx1YWUzMFx1YzgxMFx1YjRlNFx1Yzc0MCAkTiAtIDEkXHVhYzFjXHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgMFx1YmQ4MFx1ZDEzMCAkTiAtIDIkXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWJkODRcdWFlMzBcdWM4MTBcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YWNlMFx1Yjk3NFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWM3NzQgXHViNDU4XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHViODVjICRpJCAoJDAmbmJzcDtcXGxlIGkgXFxsZSBOIC0gMiQpXHViMjk0IFx1YmQ4NFx1YWUzMFx1YzgxMCAkVVtpXSRcdWM2NDAgJFZbaV0kXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjU4XHVhY2JkIFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhY2JkXHVhYzAxXHVjMmVjXHVjNzQ0IFx1YjE5Mlx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMjE4XHViNzdjXHViYzE0XHVjNTdjIFx1YzJkY1x1Yzc1OCBcdWMyZGNcdWM3YTUgXHVhZTQwIFx1YmMxNVx1YzBhY1x1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjNWM2XHViMjk0IFx1YjBhMFx1Yzc0NCBcdWM5YzBcdWM4MTVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3OTBcdWIzZDlcdWNjMjggXHVjNWM2XHViMjk0IFx1YjBhMCBcdWQ1ODlcdWMwYWNcdWI4NWMsIFx1YWU0MCBcdWJjMTVcdWMwYWNcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1ZDNkMFx1YzFjNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDNkMFx1YzFjNFx1ZDU2MCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWQ1NzRcdWM5YzRcdWIyZTQuIFx1YWU0MCBcdWJjMTVcdWMwYWNcdWIyOTQgXHViYTNjXHVjODAwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4ICRrJFx1Yjk3YyBcdWFjZTBcdWI5NzRcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWJkODRcdWFlMzBcdWM4MTBcdWM1ZDAgJGskXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWQzZDBcdWMxYzRcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM5YzFcdWM4MTEgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1Yjg1YyAkaSRcdWI5N2MgXHVkM2QwXHVjMWM0XHVkNTU4XHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCAkV1tpXSRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWU0MCBcdWJjMTVcdWMwYWNcdWI5N2MgXHViM2M0XHVjNjQwXHVjMTFjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCAkayQgKCQwIFxcbGUgayBcXGxlIE4gLSAxJCkgXHVhYzAxXHVhYzAxXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVhYzhjIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZDBcdWMxYzRcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiIiLCJvdXRwdXQiOiIiLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZSBOIFxcbGUgMTAwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlIFVbaV0sIFZbaV0gXFxsZSBOIC0gMSQgKFx1YmFhOFx1YjRlMCAkMCBcXGxlIGkgXFxsZSBOIC0gMiQpPFwvbGk+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWI0NTAgXHViZDg0XHVhZTMwXHVjODEwXHViM2M0IFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgV1tpXSBcXGxlIDEwXjkkJm5ic3A7KFx1YmFhOFx1YjRlMCAkMCBcXGxlIGkgXFxsZSBOIC0gMiQpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRVW2ldID0gMCQgKFx1YmFhOFx1YjRlMCAkMCBcXGxlIGkgXFxsZSBOIC0gMiQpPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kVVtpXSA9IGkkLCAkVltpXSA9IGkgKyAxJCAoXHViYWE4XHViNGUwICQwIFxcbGUgaSBcXGxlIE4gLSAyJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROIFxcbGUgMjAwJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+JE4gXFxsZSAyMDAwJDxcL3A+XHJcbiIsInN1YnRhc2s1IjoiPHA+JFdbaV0gPSAxJCAoXHViYWE4XHViNGUwICQwIFxcbGUgaSBcXGxlIE4gLSAyJCk8XC9wPlxyXG4iLCJzdWJ0YXNrNiI6IjxwPiRXW2ldIFxcbGUgMTAkIChcdWJhYThcdWI0ZTAgJDAgXFxsZSBpIFxcbGUgTiAtIDIkKTxcL3A+XHJcbiIsInN1YnRhc2s3IjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImN1c3RvbV9pbXBsZW1lbnRhdGlvbiI6IjxwPlx1YjJlNFx1Yzc0YyBcdWQ1NjhcdWMyMThcdWI5N2MgXHVhZDZjXHVkNjA0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuaW50NjRbXSBtaW5pbXVtX2Nsb3N1cmVfY29zdHMoaW50IE4sIGludFtdIFUsIGludFtdIFYsIGludFtdIFcpPFwvcHJlPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kTiQ6IFx1YzIxOFx1Yjc3Y1x1YmMxNFx1YzU3Y1x1Yzc1OCBcdWJkODRcdWFlMzBcdWM4MTAgXHVjMjE4PFwvbGk+XHJcblx0PGxpPiRVJCwgJFYkIDogXHVhZTM4XHVjNzc0ICROIC0gMSRcdWM3NzggXHViYzMwXHVjNWY0XHViODVjLCBcdWJkODRcdWFlMzBcdWM4MTAgJFVbaV0kXHVjNjQwICRWW2ldJFx1YjI5NCBcdWIzYzRcdWI4NWMgJGkkXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRXJDogXHVhZTM4XHVjNzc0ICROIC0gMSRcdWM3NzggXHViYzMwXHVjNWY0XHViODVjLCAkV1tpXSRcdWIyOTQgXHViM2M0XHViODVjICRpJFx1Yjk3YyBcdWQzZDBcdWMxYzRcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0IFx1ZDU2OFx1YzIxOFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViYzMwXHVjNWY0ICROJFx1Yzc0NCBcdWI5YWNcdWQxMzRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDEgJGskXHViOWM4XHViMmU0ICgkMCBcXGxlIGsgXFxsZSBOIC0mbmJzcDsxJCksIFx1Yzc3NCBcdWJjMzBcdWM1ZjRcdWM3NTggJGskXHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWJhYThcdWI0ZTAgXHViZDg0XHVhZTMwXHVjODEwXHVjNzc0IFx1YzljMVx1YzgxMSBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkM2QwXHVjMWM0XHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjZDVjXHViMzAwICRrJFx1YWMxY1x1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViM2M0XHViODVjXHViOTdjIFx1ZDNkMFx1YzFjNFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzQgXHVkNTY4XHVjMjE4XHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWQ1NWMgXHViYzg4IFx1ZDYzOFx1Y2Q5Y1x1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImN1c3RvbV9leGFtcGxlMSI6IjxwPlx1YjJlNFx1Yzc0YyBcdWQ2MzhcdWNkOWNcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cHJlPlxyXG5taW5pbXVtX2Nsb3N1cmVfY29zdHMoNSwgWzAsIDAsIDAsIDJdLCBbMSwgMiwgMywgNF0sIFsxLCA0LCAzLCAyXSk8XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWIyOTQgXHVjZDFkIDVcdWFjMWNcdWM3NTggXHViZDg0XHVhZTMwXHVjODEwXHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWMgNFx1YWMxY1x1YWMwMCAoMCwgMSksICgwLCAyKSwgKDAsIDMpLCAoMiwgNClcdWM3NDQgXHVjNzg3XHVhY2UwLCBcdWM3NzQgXHViM2M0XHViODVjXHViOTdjIFx1ZDNkMFx1YzFjNFx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVhYzAxXHVhYzAxIDEsIDQsIDMsIDJcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzZiNDhlYTAzLWY1ODUtNGI5ZS1iMzVjLTM4MDgwYWEyYThiM1wvLVwvcHJldmlld1wvXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhZDZjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWU0MCBcdWJjMTVcdWMwYWNcdWFjMDAgJGsgPSAwJFx1YzczY1x1Yjg1YyBcdWFjZTBcdWI5NzRcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVkM2QwXHVjMWM0XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YyBcdWNkMWQgXHViZTQ0XHVjNmE5XHVjNzQwIDEgKyA0ICsgMyArIDIgPSAxMFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTQwIFx1YmMxNVx1YzBhY1x1YWMwMCAkayA9IDEkXHViODVjIFx1YWNlMFx1Yjk3NFx1YmE3NCwgXHViM2M0XHViODVjIDBcdWFjZmMgXHViM2M0XHViODVjIDFcdWM3NDQgXHVkM2QwXHVjMWM0XHVkNTU4XHViYTc0IFx1Y2QxZCBcdWJlNDRcdWM2YTkgMSArIDQgPSA1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTQwIFx1YmMxNVx1YzBhY1x1YWMwMCAkayA9IDIkXHViODVjIFx1YWNlMFx1Yjk3NFx1YmE3NCwgXHViM2M0XHViODVjIDBcdWM3NDQgXHVkM2QwXHVjMWM0XHVkNTU4XHViYTc0IFx1Y2QxZCBcdWJlNDRcdWM2YTkgMVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWU0MCBcdWJjMTVcdWMwYWNcdWFjMDAgJGsgPSAzJCBcdWI2MTBcdWIyOTQgJGsgPSA0JFx1Yjk3YyBcdWFjZTBcdWI5NzRcdWJhNzQsIFx1YzViNFx1YjI5MCBcdWIzYzRcdWI4NWNcdWIzYzQgXHVkM2QwXHVjMWM0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViNTMwXHViNzdjXHVjMTFjLCA8Y29kZT5taW5pbXVtX2Nsb3N1cmVfY29zdHM8XC9jb2RlPlx1Yzc1OCBcdWI5YWNcdWQxMzRcdWFjMTJcdWM3NDAgWzEwLCA1LCAxLCAwLCAwXVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJjdXN0b21fZXhhbXBsZTIiOiI8cD5cdWIyZTRcdWM3NGMgXHVkNjM4XHVjZDljXHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm1pbmltdW1fY2xvc3VyZV9jb3N0cyg0LCBbMCwgMiwgMF0sIFsxLCAwLCAzXSwgWzUsIDEwLCA1XSk8XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWIyOTQgXHVjZDFkIDRcdWFjMWNcdWM3NTggXHViZDg0XHVhZTMwXHVjODEwXHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWMgM1x1YWMxY1x1YWMwMCAoMCwgMSksICgyLCAwKSwgKDAsIDMpXHVjNzQ0IFx1Yzc4N1x1YWNlMCwgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZDBcdWMxYzRcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YWMwMVx1YWMwMSA1LCAxMCwgNVx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYjFhMjAzMzQtYWZiMy00ZjUwLWI2NDUtNTYxMDJiZmVhZjY5XC8tXC9wcmV2aWV3XC9cIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhZTQwIFx1YmMxNVx1YzBhY1x1YWMwMCAkayA9IDAkXHVjNzNjXHViODVjIFx1YWNlMFx1Yjk3NFx1YmE3NCwgXHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWQzZDBcdWMxYzRcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjIFx1Y2QxZCBcdWJlNDRcdWM2YTlcdWM3NDAgNSArIDEwICsgNSA9IDIwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFlNDAgXHViYzE1XHVjMGFjXHVhYzAwICRrID0gMSRcdWI4NWMgXHVhY2UwXHViOTc0XHViYTc0LCBcdWIzYzRcdWI4NWMgMFx1YWNmYyBcdWIzYzRcdWI4NWMgMlx1Yzc0NCBcdWQzZDBcdWMxYzRcdWQ1NThcdWJhNzQgXHVjZDFkIFx1YmU0NFx1YzZhOSA1ICsgNSA9IDEwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTQwIFx1YmMxNVx1YzBhY1x1YWMwMCAkayA9IDIkXHViODVjIFx1YWNlMFx1Yjk3NFx1YmE3NCwgXHViM2M0XHViODVjIDAgXHViNjEwXHViMjk0IFx1YjNjNFx1Yjg1YyAyXHVjNzQ0IFx1ZDNkMFx1YzFjNFx1ZDU1OFx1YmE3NCBcdWNkMWQgXHViZTQ0XHVjNmE5IDVcdWFjMDAgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFlNDAgXHViYzE1XHVjMGFjXHVhYzAwICRrID0gMyRcdWM3NDQgXHVhY2UwXHViOTc0XHViYTc0LCBcdWM1YjRcdWIyOTAgXHViM2M0XHViODVjXHViM2M0IFx1ZDNkMFx1YzFjNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYywgPGNvZGU+bWluaW11bV9jbG9zdXJlX2Nvc3RzPFwvY29kZT5cdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQwIFsyMCwgMTAsIDUsIDBdXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImN1c3RvbV9ncmFkZXIiOiI8cD5cdWMwZDhcdWQ1MGMgXHVhZGY4XHViODA4XHVjNzc0XHViMzU0XHViMjk0IFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWIyZTRcdWM3NGMgXHVjNTkxXHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3ZFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5saW5lIDE6ICROJDxcL2xpPlxyXG5cdDxsaT5saW5lIDIgKyAkaSQgKCQwIFxcbGUgaSBcXGxlJm5ic3A7TiAtIDIkKTogJFVbaV0kICRWW2ldJCAkV1tpXSQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwZDhcdWQ1MGMgXHVhZGY4XHViODA4XHVjNzc0XHViMzU0XHViMjk0IDxjb2RlPm1pbmltdW1fY2xvc3VyZV9jb3N0czxcL2NvZGU+XHVhYzAwIFx1YjlhY1x1ZDEzNFx1ZDU1YyBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiY3VzdG9tX2F0dGFjaG1lbnQiOiI8dWw+XHJcblx0PGxpPjxhIGhyZWY9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84NjFhYWI5NC0xOGE0LTQxMTUtOTMwNS1mZTBiMmU2NDNlMDdcL1wiPnJvYWRzLnppcDxcL2E+PFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyMTg1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvYWQgQ2xvc3VyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBjaXR5IG9mIFN1cmFiYXlhLCB0aGVyZSBhcmUgJE4kIGp1bmN0aW9ucywgbnVtYmVyZWQgZnJvbSAkMCQgdG8gJE4gLSAxJC4gVGhlc2UganVuY3Rpb25zIGFyZSBjb25uZWN0ZWQgYnkgJE4gLSAxJCBiaWRpcmVjdGlvbmFsIHJvYWRzLCBudW1iZXJlZCBmcm9tICQwJCB0byAkTiAtIDIkLCBzdWNoIHRoYXQgdGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBiZXR3ZWVuIGFueSBwYWlyIG9mIGp1bmN0aW9ucyB0aHJvdWdoIHRoZSByb2Fkcy4gUm9hZCAkaSQgKCQwIFxcbGUgaSBcXGxlIE4gLSAyJCkgY29ubmVjdHMganVuY3Rpb24gJFVbaV0kIGFuZCAkVltpXSQuPFwvcD5cclxuXHJcbjxwPlRvIHJhaXNlIGVudmlyb25tZW50YWwgYXdhcmVuZXNzLCBQYWsgRGVuZ2tsZWssIGFzIHRoZSBtYXlvciBvZiBTdXJhYmF5YSwgcGxhbnMgdG8gaG9sZCBhIENhciBGcmVlIERheS4gVG8gZW5jb3VyYWdlIHRoZSBldmVudCwgUGFrIERlbmdrbGVrIHdpbGwgb3JnYW5pemUgcm9hZCBjbG9zdXJlcy4gUGFrIERlbmdrbGVrIHdpbGwgZmlyc3QgY2hvb3NlIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgJGskLCB0aGVuIGNsb3NlIHNvbWUgb2YgdGhlIHJvYWRzIHN1Y2ggdGhhdCBlYWNoIGp1bmN0aW9uIGlzIGRpcmVjdGx5IGNvbm5lY3RlZCB0byZuYnNwOzxzdHJvbmc+YXQgbW9zdDxcL3N0cm9uZz4mbmJzcDskayQgcm9hZHMgdGhhdCBhcmUgbm90IGNsb3NlZC4gVGhlIGNvc3QgdG8gY2xvc2Ugcm9hZCAkaSQgaXMgJFdbaV0kLjxcL3A+XHJcblxyXG48cD5IZWxwIFBhayBEZW5na2xlayB0byBmaW5kIHRoZSBtaW5pbXVtIHRvdGFsIGNvc3QgdG8gY2xvc2UgdGhlIHJvYWRzIGZvciBlYWNoIHBvc3NpYmxlIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyICRrJCAoJDAgXFxsZSBrIFxcbGUgTiAtIDEkKS48XC9wPlxyXG4iLCJpbnB1dCI6IiIsIm91dHB1dCI6IiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZSBOIFxcbGUgMTAwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlIFVbaV0sIFZbaV0gXFxsZSBOIC0gMSQgKGZvciBhbGwgJDAgXFxsZSBpIFxcbGUgTiAtIDIkKTxcL2xpPlxyXG5cdDxsaT5JdCBpcyBwb3NzaWJsZSB0byB0cmF2ZWwgYmV0d2VlbiBhbnkgcGFpciBvZiBqdW5jdGlvbnMgdGhyb3VnaCB0aGUgcm9hZHMuPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgV1tpXSBcXGxlIDEwXjkkJm5ic3A7KGZvciBhbGwgJDAgXFxsZSBpIFxcbGUgTiAtIDIkKTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kVVtpXSA9IDAkIChmb3IgYWxsICQwIFxcbGUgaSBcXGxlIE4gLSAyJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRVW2ldID0gaSQsICRWW2ldID0gaSArIDEkIChmb3IgYWxsICQwIFxcbGUgaSBcXGxlIE4gLSAyJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROIFxcbGUgMjAwJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+JE4gXFxsZSAyMDAwJDxcL3A+XHJcbiIsInN1YnRhc2s1IjoiPHA+JFdbaV0gPSAxJCAoZm9yIGFsbCAkMCBcXGxlIGkgXFxsZSBOIC0gMiQpPFwvcD5cclxuIiwic3VidGFzazYiOiI8cD4kV1tpXSBcXGxlIDEwJCAoZm9yIGFsbCAkMCBcXGxlIGkgXFxsZSBOIC0gMiQpPFwvcD5cclxuIiwic3VidGFzazciOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsImN1c3RvbV9pbXBsZW1lbnRhdGlvbiI6IjxwPllvdSBzaG91bGQgaW1wbGVtZW50IHRoZSBmb2xsb3dpbmcgcHJvY2VkdXJlOjxcL3A+XHJcblxyXG48cHJlPlxyXG48Y29kZT5pbnQ2NFtdIG1pbmltdW1fY2xvc3VyZV9jb3N0cyhpbnQgTiwgaW50W10gVSwgaW50W10gViwgaW50W10gVylcclxuPFwvY29kZT48XC9wcmU+XHJcblxyXG48dWw+XHJcblx0PGxpPiROJDogdGhlIG51bWJlciBvZiBqdW5jdGlvbnMgaW4gU3VyYWJheWEuPFwvbGk+XHJcblx0PGxpPiRVJCBhbmQgJFYkOiBhcnJheXMgb2Ygc2l6ZSAkTiAtIDEkLCB3aGVyZSBqdW5jdGlvbnMgJFVbaV0kIGFuZCAkVltpXSQgYXJlIGNvbm5lY3RlZCBieSByb2FkICRpJC48XC9saT5cclxuXHQ8bGk+JFckOiBhbiBhcnJheSBvZiBzaXplICROIC0gMSQsIHdoZXJlICRXW2ldJCBpcyB0aGUgY29zdCB0byBjbG9zZSByb2FkICRpJC48XC9saT5cclxuXHQ8bGk+VGhpcyBwcm9jZWR1cmUgc2hvdWxkIHJldHVybiBhIHNpbmdsZSBhcnJheSBvZiBzaXplICROJC4gRm9yIGVhY2ggJGskICgkMCBcXGxlIGsgXFxsZSBOIC0gMSQpLCB0aGUgJGskLXRoIGVsZW1lbnQgaXMgdGhlIG1pbmltdW0gdG90YWwgY29zdCB0byBjbG9zZSB0aGUgcm9hZHMgc3VjaCB0aGF0IGVhY2gganVuY3Rpb24gaXMgZGlyZWN0bHkgY29ubmVjdGVkIHRvIGF0IG1vc3QgJGskIHJvYWRzIHRoYXQgYXJlIG5vdCBjbG9zZWQuPFwvbGk+XHJcblx0PGxpPlRoaXMgcHJvY2VkdXJlIGlzIGNhbGxlZCBleGFjdGx5IG9uY2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJjdXN0b21fZXhhbXBsZTEiOiI8cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIGNhbGw6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjxjb2RlPm1pbmltdW1fY2xvc3VyZV9jb3N0cyg1LCBbMCwgMCwgMCwgMl0sIFsxLCAyLCAzLCA0XSwgWzEsIDQsIDMsIDJdKVxyXG48XC9jb2RlPjxcL3ByZT5cclxuXHJcbjxwPlRoaXMgbWVhbnMgdGhlcmUgaXMgYSB0b3RhbCBvZiAkNSQganVuY3Rpb25zIGFuZCAkNCQgcm9hZHMgY29ubmVjdGluZyB0aGUganVuY3Rpb24gcGFpcnMgJCgwLCAxKSQsICQoMCwgMikkLCAkKDAsIDMpJCwgYW5kICQoMiwgNCkkIHdpdGggY2xvc3VyZSBjb3N0cyAkMSQsICQ0JCwgJDMkLCBhbmQgJDIkLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNmI0OGVhMDMtZjU4NS00YjllLWIzNWMtMzgwODBhYTJhOGIzXC8tXC9wcmV2aWV3XC9cIiBcLz48XC9wPlxyXG5cclxuPHA+VG8gb2J0YWluIHRoZSBtaW5pbXVtIGNvc3RzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmlmIFBhayBEZW5na2xlayBjaG9zZSAkayA9IDAkLCB0aGVuIGFsbCByb2FkcyBzaG91bGQgYmUgY2xvc2VkIHdpdGggYSB0b3RhbCBjb3N0IG9mICQxICsgNCArIDMgKyAyID0gMTAkOzxcL2xpPlxyXG5cdDxsaT5pZiBQYWsgRGVuZ2tsZWsgY2hvc2UgJGsgPSAxJCwgdGhlbiByb2FkICQwJCBhbmQgcm9hZCAkMSQgc2hvdWxkIGJlIGNsb3NlZCB3aXRoIGEgdG90YWwgY29zdCBvZiAkMSArIDQgPSA1JDs8XC9saT5cclxuXHQ8bGk+aWYgUGFrIERlbmdrbGVrIGNob3NlICRrID0gMiQsIHRoZW4gcm9hZCAkMCQgc2hvdWxkIGJlIGNsb3NlZCB3aXRoIGEgdG90YWwgY29zdCBvZiAkMSQ7PFwvbGk+XHJcblx0PGxpPmlmIFBhayBEZW5na2xlayBjaG9zZSAkayA9IDMkIG9yICRrID0gNCQsIHRoZW4gbm8gcm9hZHMgbmVlZCB0byBiZSBjbG9zZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlcmVmb3JlLCB0aGUmbmJzcDs8Y29kZT5taW5pbXVtX2Nsb3N1cmVfY29zdHM8XC9jb2RlPiZuYnNwO3Byb2NlZHVyZSBzaG91bGQgcmV0dXJuICRbMTAsIDUsIDEsIDAsIDBdJC48XC9wPlxyXG4iLCJjdXN0b21fZXhhbXBsZTIiOiI8cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIGNhbGw6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjxjb2RlPm1pbmltdW1fY2xvc3VyZV9jb3N0cyg0LCBbMCwgMiwgMF0sIFsxLCAwLCAzXSwgWzUsIDEwLCA1XSlcclxuPFwvY29kZT48XC9wcmU+XHJcblxyXG48cD5UaGlzIG1lYW5zIHRoZXJlIGlzIGEgdG90YWwgb2YgJDQkIGp1bmN0aW9ucyBhbmQgJDMkIHJvYWRzIGNvbm5lY3RpbmcgdGhlIGp1bmN0aW9uIHBhaXJzICQoMCwgMSkkLCAkKDIsIDApJCwgYW5kICQoMCwgMykkIHdpdGggdGhlIGNsb3N1cmUgY29zdHMgJDUkLCAkMTAkLCBhbmQgJDUkIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9iMWEyMDMzNC1hZmIzLTRmNTAtYjY0NS01NjEwMmJmZWFmNjlcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48cD5UbyBvYnRhaW4gdGhlIG1pbmltdW0gY29zdHM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+aWYgUGFrIERlbmdrbGVrIGNob3NlICRrID0gMCQsIHRoZW4gYWxsIHJvYWRzIHNob3VsZCBiZSBjbG9zZWQgd2l0aCBhIHRvdGFsIGNvc3Qgb2YgJDUgKyAxMCArIDUgPSAyMCQ7PFwvbGk+XHJcblx0PGxpPmlmIFBhayBEZW5na2xlayBjaG9zZSAkayA9IDEkLCB0aGVuIHJvYWQgJDAkIGFuZCByb2FkICQyJCBzaG91bGQgYmUgY2xvc2VkIHdpdGggYSB0b3RhbCBjb3N0IG9mICQ1ICsgNSA9IDEwJDs8XC9saT5cclxuXHQ8bGk+aWYgUGFrIERlbmdrbGVrIGNob3NlICRrID0gMiQsIHRoZW4gZWl0aGVyIHJvYWQgJDAkIG9yIHJvYWQgJDIkIHNob3VsZCBiZSBjbG9zZWQgd2l0aCBhIHRvdGFsIGNvc3Qgb2YgJDUkOzxcL2xpPlxyXG5cdDxsaT5pZiBQYWsgRGVuZ2tsZWsgY2hvc2UgJGsgPSAzJCwgdGhlbiBubyByb2FkcyBuZWVkIHRvIGJlIGNsb3NlZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZWZvcmUsIHRoZSZuYnNwOzxjb2RlPm1pbmltdW1fY2xvc3VyZV9jb3N0czxcL2NvZGU+Jm5ic3A7cHJvY2VkdXJlIHNob3VsZCByZXR1cm4gJFsyMCwgMTAsIDUsIDBdJC48XC9wPlxyXG4iLCJjdXN0b21fZ3JhZGVyIjoiPHA+VGhlIHNhbXBsZSBncmFkZXIgcmVhZHMgdGhlIGlucHV0IGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmxpbmUgJDEkOiAkTiQ8XC9saT5cclxuXHQ8bGk+bGluZSAkMiArIGkkICgkMCBcXGxlIGkgXFxsZSBOIC0gMiQpOiAkVVtpXSBcXDsgVltpXSBcXDsgV1tpXSQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgc2FtcGxlIGdyYWRlciBwcmludHMgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBhcnJheSByZXR1cm5lZCBieSZuYnNwOzxjb2RlPm1pbmltdW1fY2xvc3VyZV9jb3N0czxcL2NvZGU+LjxcL3A+XHJcbiIsImN1c3RvbV9hdHRhY2htZW50IjoiPHVsPlxyXG5cdDxsaT48YSBocmVmPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvODYxYWFiOTQtMThhNC00MTE1LTkzMDUtZmUwYjJlNjQzZTA3XC9cIj5yb2Fkcy56aXA8XC9hPjxcL2xpPlxyXG48XC91bD5cclxuIn1d

샘플 그레이더

샘플 그레이더는 입력을 다음 양식으로 읽는다.

  • line 1: $N$
  • line 2 + $i$ ($0 \le i \le N - 2$): $U[i]$ $V[i]$ $W[i]$

샘플 그레이더는 minimum_closure_costs가 리턴한 배열을 한 줄에 출력한다.

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.