6158 : 트리 DP — 색칠

시간 2.000s · 메모리 256MB · 제출 0 · 정답 0

코드제출 문제 풀기

채점기록 통계 묻고답하기

인접한 부모와 자식 노드가 서로 다른 색을 갖도록 트리를 칠하는 경우의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)과 사용할 색의 수 K (1 ≤ K ≤ 10)가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.

서로 다른 색으로 칠하는 경우의 수를 1,000,000,007로 나눈 나머지를 출력합니다.

3 3
1 2
2 3