Informatica Online Judge

  헛간 칠하기 [2170 / 087A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 5


The Champion of this Problem (C++) : icp1481 - 6ms / 861byte
My Best Submission (C++) : N/A

[USACO (Nick Wu)]

Background

농부 존은 N개의 헛간을 가지고 있다. 이 헛간들 중 K개의 헛간들은 이미 칠해져 있으며 나머지는 아직 색이 칠해져있지 않다.

농부 존은 남은 농장들을 칠하려고 한다. 이 때 쓸 수 있는 색깔은 오직 빨, 녹, 파로 3가지 색깔뿐이다.

존은 화려한 것을 좋아하므로 인접한 두 헛간을 같은 색으로 칠하기는 싫다.

존의 헛간들은 N-1개의 길로 연결되어 있으며 모든 헛간들은 다른 헛간으로 이 길을 이용해서 이동할 수 있다. (양방향 이동 가능)

농부 존은 자신이 원하는대로 헛간들을 칠하는 방법의 수를 알고싶어한다.

이 값을 구하는 프로그램을 작성하시오. 값이 너무 커질 수 있으므로 10억 7로 나눈 나머지를 구하는 프로그램을 작성하면 된다.

Input

$N$ $K$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_{n-1}$ $y_{n-1}$
$b_1$ $c_1$
:
$b_k$ $c_k$

2번째 줄부터 n번째 줄까지의 내용은
헛간 x와 헛간 y는 연결되었음을 의미한다.

n+1번째 줄부터 n+k번째 줄까지의 내용은
헛간 b는 c색으로 칠해져있음을 의미한다.

[입력값의 정의역]
$0 ≤ K ≤ N ≤ 100,000$
$1 ≤ x, y ≤ N$
$1 ≤ b ≤ N ; 1 ≤ c ≤ 3$

Output

인접한 헛간을 같은 색이 아니도록 칠하는 서로 다른 경우의 수를 구한다. 답을 10억 7로 나눈 값을 출력한다.

IO Example

입력
4 1
1 2
1 3
1 4
4 3

출력
8

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]