kinssang   2년 전

전체 트리의 root를 1번 node로 두고,
dp[i][j] = i번 node를 root로 하는 subtree에서 j개 만큼의 원소를 제거할 때 최소한으로 필요한 간선 제거 횟수.
value[i] = i번 node를 root로 하는 subtree의 원소의 갯수(크기)
로 dp를 구한 다음, 답의 경우는 i가 전체 트리의 root인 경우와, i가 전체 트리의 root가 아닌 경우로 나누어서,
i가 root인 경우는 dp[i][N-M],
i가 root가 아닌 경우는 전체 트리에서 서브트리로 떨어져 나오는데 간선 제거를 한번 했으므로, 1+dp[i][value[i]-M]
으로 생각해서 이 중 최소값을 구하는 식으로 답을 정했는데요.
시작하자마자 계속 틀렸습니다가 뜹니다. 혹시 반례를 얻을 수 있을까요?

kinssang   2년 전

dfs를 애초에 잘못짜서 일자형 같은 경우에는 제대로 계산이 안됐었습니다. 해결했습니다

댓글을 작성하려면 로그인해야 합니다.