을 크기 순서대로 정렬하자. 모든 에 대해 에서 로 향하고 비용이 인 간선을 추가하고, 에서 으로 향하고 비용이 인 간선을 추가하였다고 하자. 이때 음수 비용 사이클은 존재하지 않고, 또한 와 같은 경로를 통해 모든 정점 에 대해 주어진 을 최소비용으로 사용하여 에 도착할 수 있다.
한편, 음수 비용 간선을 더 추가할 수 없다. 에 대해 방향 음수 간선을 추가한다면 에 모순이다. 방향 음수 비용 간선에서 비용의 절대치를 늘릴 수 없는데, 까지 도달하는데의 최소 비용이 항상 보다 작아지고 이는 모순이다.
양수 비용 간선의 비용 합은 조건에 의해 적어도 이어야 한다. 따라서 위 구성은 농장의 비용을 최소화하고, 이 비용이 원하는 답이 된다. 를 계산하고 여기에 을 더하면 원하는 답이다. 정렬하는데 사용된 시간은 이고, 원하는 답을 계산하기 위해 만큼의 시간을 사용한다.
1540B Tree Array
뿌리 정점을 하나 고정하였을 때, 모든 에 대해 가 보다 먼저 등장할 확률 을 계산하여 합 을 구하면 이는 이 뿌리 정점에 대해 나타날 수 있는 모든 tree array에서 나타나는 반전inversion 개수의 기댓값이다. 구한 개의 합의 평균이 원하는 답이 된다.
는 와 의 최소 공통 조상에 대한 상대 깊이에만 의존한다. 와 를 연결하는 경로 위에 있지 않은 정점들을 선택하는 순서는 사이의 순서에 영향을 주지 않기 때문이다. 의 상대 깊이를 각각 라고 하자. 이때 반전 개수의 기댓값을 라고 할 때, 다음 점화식을 얻을 수 있다.
이는 메모이제이션으로 시간안에 전처리 후 시간을 사용해서 결과를 얻을 수 있다. 개의 쌍에 대해 최소 공통 조상을 구하는 데에 시간이 사용되고, 이를 개의 정점에 대해 그를 뿌리로 고정하여 반복하므로 전체 답을 구하는 데에 시간이 사용된다.
한편, 최소 공통 조상을 매번 계산하여야 해서 로그 항이 곱해진다. 전처리를 통해 쌍에 대해 최소 공통 조상을 시간 복잡도로 계산할 수 있으므로 는 메모이제이션 이후 시간 복잡도로 계산할 수 있다. 따라서 시간 복잡도 풀이도 존재한다.
