RiseOJ – 헛간 색칠하기

설명

농부 존은 $$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$$ 로 나눈 나머지를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 barnpainting.in · 출력을 쓸 파일 barnpainting.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Gold

올림피아드 > USACO > 2017-2018 > December > Gold

태그

JudgeUSACO

헛간 색칠하기

평가 및 의견

풀이 제출