문제 링크
https://www.acmicpc.net/problem/12928
풀이
트리에서 길이가 2인 단순 경로의 개수는 노드$i$에 연결된 간선의 개수가 $d_i$개라고 할 때 $\sum {d_i \choose 2}$입니다.
$N$과 $S$의 크기가 매우 작습니다. 노드 $n$개로 이루어진 트리에서 $s$개의 단순 경로가 있을 수 있는지 모든 $NS$에 대해 확인해 볼 수 있습니다.
$D(n, s) = $ 트리를 이루고 남은 정점이 $n$개이고 현재까지 만들어진 경로의 개수가 $s$개로 만드는 것이 가능한지 로 DP를 정의합니다. 처음에는 크기 $2$짜리 트리를 하나 놓는다고 생각하고 시작합니다. 이때 경로의 개수는 $0$개입니다. $(D(N-2, 0))$ 그 뒤에는 degree가 $1$인 정점에(늘 존재함) $i$개의 정점을 붙여 경로의 개수를 ${i+1 \choose 2}$ 만큼 추가하여 $D(n-i, c+{i+1 \choose 2})$로 전이합니다. $D()$ 함수를 최대 $NS$번 방문하고 $i$가 $[1, n]$을 순회하기 때문에 $O(N^2S)$ 풀이입니다.
전체 코드
1 |
|