정점 수가 $N$인 트리가 주어진다. 간선에 방향을 부여해 이동할 수 있는 정점 쌍의 수를 최대화하라.사실 최솟값도 구해야하지만 쉽게 $N-1$임을 알 수 있으므로 생략했습니다. 간선의 방향은 어떤 정점 $r$을 기준으로 어떤 서브트리는 내려가는 방향, 어떤 서브트리는 올라오는 방향으로 하는 것이 최적이다. 증명은 만약 아니라면, 간선의 방향을 바꾸어 증가시킬 수 있다는 것으로 충분합니다.이제 그러면 $r$을 중심으로 나머지 서브트리를 최대한 잘 반띵하는 것이 목표가 됩니다.과연 어떤 정점 $r$을 잡는 것이 이득일까요? $r = cent$일 때 최적해를 가진다 만약 사이즈가 $N/2$보다 큰 서브트리가 있다면, 그 방향으로 한 칸 움직이는 것으로 더욱 최적임을 알 수 있습니다. 그러면 ..