谷仓涂色(Barn Painting G)

题目描述

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

样例输出 #1

8

数据范围

请使用高效率算法及 64 位整数（long long）避免溢出。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接