17674 특별관광도시

$N$개의 정점이 있는 트리 위에, 간선에 가중치가 유향으로 2개씩 붙어있습니다. 즉, $a->b$ 가중치와 $b->a$ 가중치가 따로 붙어있습니다. 어떤 정점을 특별관광도시로 선택하면, 모든 간선의 특별관광도시로 오는 방향의 가중치가 비용에 더해집니다. $K = 1, 2, \dots , N$에 대해, $K$개의 특별관광도시를 선택할 때 비용의 최댓값을 구하시오.

물론 한번 가중치가 더해진 간선이 새로 특별관광도시를 선택한다고 가중치가 또 더해지진 않습니다.

 

 

 

---

 

 

 

$K=1$일 때는 간단히 tree DP로 구할 수 있습니다. $K=2$의 경우는 어떻게 할까요? 신기하게도 이도 tree DP로 구할 수 있습니다.

미리 $f(x)=(x하나만 먹었을 때 가중치)$를 계산해둡시다.

만약 어떤 정점 $x$를 한쪽 끝으로 가진다고 생각해봅시다. 다른 한쪽 끝이 $y$라면, 이때의 총 비용은

$[f(x) + f(y) + (x-y 경로의 양방향 가중치 합)]/2$ 이 됩니다.

한 쪽 끝을 고정하면 반대쪽은 tree DP로 구해 줄 수 있습니다. 

제일 신기한 점은 이를 트리의 지름을 찾듯이 $K=2$일 때 해를 구해 줄 수 있다는 것입니다.

아무 정점 $a$를 잡고, $a$에서의 반대쪽 끝을 찾습니다. 이를 $v$라 하면, $v$에서 다시 해를 찾아 나온게 $K=2$일 때

해가 됩니다. 흠.. 증명은 잘 모르겠습니다.

 

$K\geq3$ 일 때를  생각해봅시다. 이 경우는 뭔가 수족관이 될 것 같습니다. 좀 더 엄밀하게는,

 

만약 최적해와 $K=2$에서 수족관을 해 나온 최적해가 겹치는 정점이 있다면, 그 정점에서 새롭게 수족관을 하면 최적해가 수족관 해임이 보여집니다.

 

만약 겹치지 않는다면 적절히 한 도시를 옮겨서  모순을 발견할 수 있습니다.

 

 

그러므로 $K\geq3$ 일 때는, $K=2$해의 한쪽 끝에서 수족관을 하면 됩니다.

 

priority queue를 이용해 구현하면 총 시간복잡도는 $O( NlogN )$입니다.