문제의 의도는 트리에서의 최소 vertex cover 크기를 다이나믹 프로그래밍으로 구하라는 것 같지만, 문제에서 아래의 표현이 잘못 해석될 여지가 있어 보입니다.

한 도시에 경찰서를 세우면 해당 도시와 그 도시에 연결된 양방향 도로들로 연결된 도시들을 감시할 수 있다.

예를 들어, 아래와 같은 입력 케이스가 주어질 경우

6

1 2

2 3

1 4

4 5

5 6

2번 도시에 경찰서를 세우면 도로로 연결된 1번과 3번 도시는 모두 감시할 수 있고, 5번 도시에 경찰서를 세우면 도로로 연결된 4번과 6번 도시를 모두 감시할 수 있으므로 최소 2개의 경찰서만 필요하다고 답을 내놓아도 문제의 표현에 어긋나지 않습니다.

그러나 이 케이스 입력에 관해 2를 답으로 출력하는 코드를 제출하면 "틀렸습니다"가 뜨고, 3으로 출력해야 "맞혔습니다"로 뜹니다.

다시 말해서 문제에서는 경찰서를 세우지 않은 도시가 두 개 이상 서로 인접하지 않아야 한다는 것을 요구하고 있지만, 문제의 단순 표현으로만 봤을 때는 해석 상 문제가 있어 보입니다.

이러한 여지 없이 트리를 이용한 다이나믹 프로그래밍으로 트리에서의 최소 vertex cover 구하는 문제로 해석할 수 있도록 위의 표현을 "경찰서를 세우지 않은 도시가 두 개 이상 서로 인접하지 않도록 경찰서를 세워야 한다"와 같은 표현으로 수정해야 한다고 생각합니다.

부탁드립니다.