[중등부] 2024 KOI 2차대회 대비 모의고사 (1주차)

1번부터 N번까지 번호가 붙은 N개의 마을이 있다.

각 마을은 0개 이상 N-1개 이하의 마을과 연결이 되어 있을 수 있다.

이 마을들을 오고가며 장사를 하는 두 개의 상단이 있는데, 두 상단은 합의 끝에 각자의 구역을 결정하여 장사를 하는 영역이 겹치지 않게 하기로 하였다.

이동의 효율성을 위하여 각자의 구역 내의 모든 마을은 연결이 되어 있어야하는데, 여기서 연결이란 하나의 마을에서 다른 마을로 이동하는데 있어서 다른 구역의 마을을 통하지 않아도 됨을 의미한다.

만약 위와 같은 형태로 마을들이 연결되어 있다면, 하나의 상단의 구역이 [1, 2, 3, 4]가 되고, 다른 상단의 구역이 [5, 6]이 된다면 5번 마을과 6번 마을이 연결되지 않기에 이는 불가능한 구역 분할이다.

구역을 [1, 3, 4]와 [2, 5, 6]으로 나누거나 [1, 2, 3, 4, 5]와 [6]으로 나누는 것은 가능하다.

두 상단 모두 최소 하나의 마을은 구역으로 받아야해서 [1, 2, 3, 4, 5, 6]과 [\ ]로 나누는 것은 불가능하다.

1번 마을의 인구는 A_1명, 2번 마을의 인구는 A_2명, i번 마을의 인구는 A_i명이 있다. (1 \le i \le N)

두 상단이 인구수의 차이가 최소가 되도록 구역을 나누게 된다면 그 인구수의 차이가 어떻게 되는지 알아보자.