레이팅 미적용농부 존은 \(N\)개의 헛간 (\(1 \le N \le 10^5\))이 있는 큰 농장을 가지고 있는데, 일부 헛간은 이미 색칠되어 있고 일부는 아직 색칠되지 않았다. 농부 존은 남은 헛간들을 색칠하여 모든 헛간이 색칠되도록 하고 싶지만, 사용할 수 있는 페인트 색은 세 가지뿐이다. 게다가 그의 우승 소 베시는 서로 직접 오갈 수 있는 두 헛간이 같은 색이면 혼란스러워하므로, 이런 상황이 생기지 않도록 해야 한다.
\(N\)개의 헛간 사이의 연결은 어떤 '사이클'도 이루지 않음이 보장된다. 즉, 어떤 두 헛간 사이에도 한쪽에서 다른 쪽으로 가는 연결의 나열이 최대 하나만 존재한다.
농부 존이 아직 색칠되지 않은 남은 헛간들을 색칠하는 방법은 몇 가지인가?
Problem credits: Nick Wu
Problem credits: Nick Wu
첫째 줄에 두 정수 \(N\)과 \(K\) (\(0 \le K \le N\))가 주어지는데, 각각 농장의 헛간 수와 이미 색칠된 헛간 수이다.
다음 \(N-1\)개의 줄에 각각 두 정수 \(x\)와 \(y\) (\(1 \le x, y \le N, x \neq y\))가 주어지며, 헛간 \(x\)와 \(y\)를 직접 연결하는 길을 의미한다.
다음 \(K\)개의 줄에 각각 두 정수 \(b\)와 \(c\) (\(1 \le b \le N\), \(1 \le c \le 3\))가 주어지며, 헛간 \(b\)가 색 \(c\)로 칠해져 있음을 의미한다.
직접 연결된 어떤 두 헛간도 같은 색이 아니도록 남은 헛간들을 색칠하는 올바른 방법의 수를 \(10^9 + 7\)로 나눈 나머지를 출력한다.
barnpainting.in · 출력을 쓸 파일 barnpainting.out4 1
1 2
1 3
1 4
4 38riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > December > Gold