BOJ 31232 삼국지, BOJ 31750 Split the GSHS 3 (P2,P1)

두 문제는 다음과 같다.

트리에서 간선을 두 개 끊어서 세 컴포넌트로 나눌 때 각각 컴포넌트의 가중치 합을 a,b,c(a<=b<=c)라 하자.

BOJ 31232는 |a-b| + |b-c| + |c-a|의 최솟값을, BOJ 31750은 abc의 최댓값을 구하는 문제이다.

뭔가 달라보이지만 각각 절댓값을 풀어보고 산술기하평균을 이용하면 둘 다 최대한 a,b,c가 1/3 * (가중치 합)에 가까워야 최적이라는 사실을 알 수 있고 비슷하게 풀이할 수 있다. (일단 필자는 31232 AC 코드에서 구하는 값만 바꿔 31750도 AC를 띄웠다)

 

끊을 두 간선이 서브트리 상에서 포함관계일 경우와 아닐 경우를 나누자.

S를 트리 전체의 가중치 합, T[x]를 x 서브트리의 가중치 합이라고 하자.

일단 포함 관계가 아닐 경우는, 각 정점의 서브트리를 기준으로 남은 구간을 최대한 균등하게 끊어야 최적이다. 이건 현재 보고 있는 정점을 x라 할 때, (S-T[x])/2에 최대한 가깝도록 나누는 것과 같고, 이건 set에 전위순회/후위순회로 가능한 후보를 관리하면서 계산해줄 수 있다.

포함 관계일 경우는 자기 서브트리 내부에서 하나 끊어야 한다. 이것도 식을 잘 풀어보면 T[x]/2에 최대한 가깝게 만드는 것이 최적이고, 이건 어떻게든 잘 구해주면 되는데 필자는 머지 소트 트리에 오일러 투어를 때려박아서 자기 서브트리 내부에서 최적을 구할 수 있도록 구현했다. 이 때 [l,r]에서 x랑 가장 가까운 원소랑 x의 차이를 리턴하는 머지 소트 트리를 구현해야 한다.

이렇게 풀면 시간 복잡도는 O(Nlog^2N)이다.