목록트리dp (1)
N coding
15940_네트워크 연결
ucpc c번 구현이 극혐이긴한데 또 생각보다 별거 없기도 하다. 내가 https://www.acmicpc.net/problem/13016 문제를 푼거랑 비슷한 방식의 트리dp를 사용하면 된다. ucpc 당시에는 원래 그래프에서 트리의 지름을 하나 구하고 트리의 지름에 속하지 않는 노드를 가지고 다시 sub지름을 구해서 잘 연결해준다. 로 접근했었는데 이러면 트리에 같은 크기를 갖는 지름이 여러개 있을 경우 어떤 지름을 원래 지름으로 선택하느냐에 따라서 최대값이 이상하게 나올 수 있다. 그래서 정해는 모든 간선을 잘라본다. 이다. 근데 모든 간선을 자를때마다 subtree의 지름과 그 subtree를 제외한 나머지 트리의 지름을 구해서 연결하면 O(n^2)이 된다. 본선당시에 다들 n^2까진 생각했을 것..
PS
2018. 8. 29. 22:05