Barn Painting

题目描述

农夫 John 有一个很大的农场，里面有 $N$ 个牛棚（$1 \le N \le 10^5$），其中一些已经被涂色，另一些还没有。农夫 John 想给剩余的牛棚涂色，使得所有牛棚都被涂上颜色，但他只有三种可用的油漆颜色。 此外，如果两个能够直接到达彼此的牛棚颜色相同，他的获奖奶牛 Bessie 就会感到困惑，因此他希望确保这种情况不会发生。 保证这 $N$ 个牛棚之间的连接不形成任何“环”。也就是说，在任意两个牛棚之间，最多只有一条通过连接从一个到达另一个的路径序列。 问农夫 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$ 取模，要求任意两座直接相连的牛棚颜色都不相同。

4 1
1 2
1 3
1 4
4 3

8

提示

题目来源：Nick Wu

标签: USACO|2017|Gold

来源

USACO|2017|Gold