아래의 그림처럼 두 노드 p,q 가 있고, 그 사이에 톨게이트를 설치하는 경우를 생각해보자
p 를 포함한 왼쪽 부분 트리의 인구수의 합을 a, 맛집 수의 합을 b, q를 포함한 오른쪽 부분 트리의 인구수의 합을 c, 맛집 수의 합을 d라 하자. 가장 많은 통행료 수입을 기대하기 위 한 톨게이트의 위치는 가중치 ad+bc 가 최대가 되는 곳을 선택해야한다.
따라서 주어진 그래프가 일직선인 경우와 트리인 경우는 누적된 합을 이용하여 O(N)에 간단히 계산할 수 있다.
1)O(N^2)
각 도시 v에 대해서 BFS로 각 도시에 이르는 최단 거리를 구한다. 거리가 먼 곳부터 역추적을 하면서 인구수와 맛집 수를 누적한다. 역추적을 하는 경로 상의 간선에 시작점 v의 인 구수와 맛집 수를 서로 곱해 더해준다. 이렇게 모든 도시에 대해서 BFS를 돌리면 모든 간 선에 가중치들이 계산되고, 가중치 값이 최댓값이 되는 간선을 찾을 수 있다.2)O(N+M)
임의의 p,q에 대해 ad+bc의 값을 계산하고, p나 q에 인접한 간선의 가중치를 계산할 때 에는 a,b,c,d를 구성하는 인자가 1~2개가 가감되므로 이를 이용하여 중복된 계산을 줄여 선형 시간에 계산할 수 있다.
톨게이트는 트리 위의 간선이나 사이클 위의 간선에 설치할 수 있다.
트리의 경우 가중치를 계산하는 방법은 트리 위를 순서대로 순회하며 값을 계산할 수 있다.
사이클의 경우에는, 하나의 사이클이 있을 때, 그 사이클을 구성하는 정점 vk 에 대 해서 해당 정점에 포함된 부분 그래프의 인구수와 맛집의 수를 누적하여 저장해둔다. 사이클은 대칭성을 가지므로 v1에 대해 사이클 내에서 가장 먼 점을 찾았다면 계산한 a,b,c,d 값을 들고 다니면서 인접한 vk들에 대해 모든 a,b,c,d 값을 선형 시간에 계산할 수 있다.
단, 짝수 길이의 사이클인 경우 사이클 내에서 가장 먼 점이 2개가 생기므로, 인구수나 맛집 수를 처음에 입력받을 때 2를 곱하여 저장한 다음, 기댓값 계산을 ad + bc 값을 2로 나누어주어 계산을 하면 실수연산을 피할 수 있다.