블로그 이사 중입니다 >> gumgood.github.io

C++11 Tree DP DP[i][0] = i번째 마을이 우수마을이 아닐 때, i번쨰 마을을 root로 하는 subtree에서 최대 마을 주민 수DP[i][1] = i번째 마을이 우수마을일 때, i번쨰 마을을 root로 하는 subtree에서 최대 마을 주민 수 라고 정의하면, DP[i][0] = 자손들이 우수마을이거나 아닐 때 최대 값들의 합DP[i][1] = 자손들이 우수마을이면 안 되는 경우 중 최대 값들의 합 + i번째 마을 주민 수 이다. 명료하게 점화식으로 나타내면,

C++11 트리의 지름은 DFS 두 번으로 구할 수 있다. 증명을 여러 개 봤지만 직관적으로 와닿지는 않는다. 다음 명제만 명확하게 증명하면 직관적으로 이해할 수 있을 것 같다. '어떤 정점에서 가장 먼 정점은 트리의 지름에 포함된다'