505020 - 填树

【题目描述】填树(tree)

有一棵n个节点的无根树,刚开始树上每个节点的权值均为0。KK想对这棵树进行一些修改,他会任选一个节点作为初始的当前节点,然后重复以下动作: 将当前节点i的权值修改为一个正整数x,需满足li≤x≤ri。其中li,ri是输入中给出的两个正整数。 结束修改过程,或移动到一个与当前节点相邻的权值为0的节点(如果不存在这样的节点,则必须结束修改过程)。 现在 KK 有两个问题: 在修改结束后,可以得到多少棵不同的树,满足树上非零权值的最大值和最小值的差小于等于K?其中K是输入中给出的一个正整数。 这些满足条件的树的权值之和为多少?(树的权值定义为这棵树上所有节点的权值之和) 你需要输出这两个问题的答案模10^9+7。我们认为两棵树不同当且仅当至少存在一个节点的权值不同。 温馨提示: KK 至少会修改一个节点(初始节点)。 实质上KK会修改树上的任意一条路径,最后需要满足这条路径上的点的权值最大值和最小值之差小于等于K。

输入

第一行两个正整数n和K,表示节点数和权值差的最大值。 接下来n行,每行两个正整数li和ri,表示第i个节点修改后权值的最小值和最大值。 接下来n−1 行,每行两个正整数ui和vi,表示节点ui和vi之间有一条边。数据保证形成一棵树。

输出

输出两行,每行一个整数,分别表示第一问和第二问的答案模10^9+7的值。注意,如果你不打算回答第二问,请在第二行任意输出一个整数。如果输出文件只有一行,则可能会因格式不符合要求被判0分。

样例

输入

3 1
2 3
3 5
4 6
1 2
1 3

输出

14
78

提示

【样例说明】 表5.1中列出了全部14棵满足条件的树,将这些树的权值加起来为78。 表5.1

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题