题目描述 Farmer John 有一个大型农场，农场里有 N 个谷仓（1<= N <= 10^5），其中一些已经上色，一些尚未上色。Farmer John 想要给剩下的谷仓上色，使得所有谷仓都被上色，但他只有三种颜色的油漆可用。此外，他的奶牛贝西（Bessie）如果看到两个可以直接到达彼此的谷仓颜色相同，就会感到困惑，所以他希望这种情况不会发生。 可以保证，N 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间，最多只有一条连接路径。 Farmer John 有多少种方式可以给剩下的未上色的谷仓上色？ 输入格式 第一行包含两个整数 N 和 K（0 <= K <= N），分别表示农场上的谷仓数量和已经上色的谷仓数量。 接下来的 N-1 行，每行包含两个整数 x 和 y（1 <= x，y <= N ，x != y），描述一条直接连接谷仓 x 和谷仓 y 的路径。 接下来的 K 行，每行包含两个整数 b 和 c（1 <= b <= N，1 <= c <= 3），表示谷仓 b 已经被涂上了颜色 c。 输出格式 计算给剩下的未上色谷仓上色的合法方式数量，结果需要对 10^9+7 取模，以确保没有两个直接相连的谷仓颜色相同。