染色

题目描述 你有一棵𝑛𝑛个点的树，一开始所有点的颜色都是0。你要执行𝑚𝑚次操作，第𝑖𝑖次操作， 你会将所有与𝑥𝑥𝑖𝑖 距离不超过𝑑𝑑的点染上颜色𝑖𝑖，其中𝑑𝑑是一个0到𝑑𝑑𝑖𝑖 之间均匀随机的整 数。

你想知道，𝑚𝑚次操作之后，整棵树期望有多少个同色连通块。

输出答案对109 + 7取模的结果。也就是如果答案表示成为𝑝𝑝/𝑞𝑞，那么输出 𝑝𝑝 × 𝑞𝑞 −1 mod 109 + 7。

输入格式 第一行两个整数𝑛𝑛, 𝑚𝑚。

接下来𝑛𝑛 − 1行，每行两个整数𝑢𝑢, 𝑣𝑣，表示树上的一条边。

接下来𝑚𝑚行，每行两个整数𝑥𝑥𝑖𝑖 , 𝑑𝑑𝑖𝑖 。

输出格式 输出𝑛𝑛行，每行一个数表示答案。

样例输入 1 5 5 1 2 1 3 2 4 2 5 1 1 2 0 3 2 4 5 5 3

样例输出 1 250000004

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1满足𝑛𝑛 ≤ 5, 𝑚𝑚 ≤ 15。 测试点2,3满足𝑛𝑛, 𝑚𝑚 ≤ 15。

测试点4,5满足给定的树是一条链。

测试点6,7满足𝑛𝑛, 𝑚𝑚 ≤ 100。

对于所有数据，满足1 ≤ 𝑛𝑛, 𝑚𝑚 ≤ 2000,1 ≤ 𝑥𝑥𝑖𝑖 ≤ 𝑛𝑛, 0 ≤ 𝑑𝑑𝑖𝑖 ≤ 𝑛𝑛。