P83830

谷仓涂色

难度 未定 初三 动态规划入门 树形
讨论 统计 5通过 13提交 38.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

Farmer John 有一个大农场,农场上有 N 个谷仓(1 \le N \le 10^5),其中一些已经涂色,另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色,使得所有谷仓都被涂色,但他只有三种可用的油漆颜色。此外,他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同,会感到困惑,因此他希望确保这种情况不会发生。

保证 N 个谷仓之间的连接不会形成任何“环”。也就是说,任意两个谷仓之间最多只有一条连接路径。

Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色?

输入

第一行包含两个整数 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,要求任何两个直接相连的谷仓颜色不同。

样例

样例 1
输入
4 1
1 2
1 3
1 4
4 3
输出
8

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交