UOJ Logo Universal Online Judge

UOJ

#735. 【统一省选2022】填树

附件下载 统计

有一棵 $n$ 个节点的无根树,刚开始树上每个节点的权值均为 $0$。KK 想对这棵树进行一些修改,他会任选一个节点作为初始的当前节点,然后重复以下动作:

  1. 将当前节点 $i$ 的权值修改为一个正整数 $x$,需满足 $l_i \le x \le r_i$。其中 $l_i, r_i$ 是输入中给出的两个正整数。
  2. 结束修改过程,或移动到一个与当前节点相邻的权值为 $0$ 的节点(如果不存在这样的节点,则必须结束修改过程)。

现在 KK 有两个问题:

  1. 在修改结束后,可以得到多少棵不同的树,满足树上非零权值的最大值和最小值的差小于等于 $K$?其中 $K$ 是输入中给出的一个正整数。
  2. 这些满足条件的树的权值之和为多少?(树的权值定义为这棵树上所有节点的权值之和)

你需要输出这两个问题的答案模 $10^9 + 7$。我们认为两棵树不同当且仅当至少存在一个节点的权值不同。

温馨提示:

  1. KK 至少会修改一个节点(初始节点)。
  2. 实质上 KK 会修改树上的任意一条路径,最后需要满足这条路径上的点的权值最大值和最小值之差小于等于 $K$。

输入格式

第一行两个正整数 $n, K$,表示节点数和权值差的最大值。

接下来 $n$ 行,每行两个正整数 $l_i, r_i$,表示第 $i$ 个节点修改后权值的最小值和最大值。

接下来 $n - 1$ 行,每行两个正整数 $u_i, v_i$,表示节点 $u_i$ 和 $v_i$ 之间有一条边。数据保证形成一棵树。

输出格式

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

样例一

input

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

output

14
78

explanation

$~$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$ $14$
节点 $1$ $2$ $3$ $2$ $3$ $3$ $3$ $3$ $3$ $0$ $0$ $0$ $0$ $0$ $0$
节点 $2$ $0$ $0$ $3$ $3$ $4$ $0$ $4$ $3$ $3$ $4$ $5$ $0$ $0$ $0$
节点 $3$ $0$ $0$ $0$ $0$ $0$ $4$ $4$ $4$ $0$ $0$ $0$ $4$ $5$ $6$

表格中列出了全部 $14$ 棵满足条件的树,将这些树的权值加起来为 $78$。

样例二、三

见附件下载。

数据范围与提示

对于 $100\%$ 的数据,$1 \le n \le 200, 1 \le l_i \le r_i \le 10^9, 1 \le K \le 10^9$。

测试点 $n\le$ $r_i,K\le$ 其他限制
$1$ $5$ $10$
$2\sim 3$ $30$ $10^9$
$4$ $30$ $500$
$5\sim 6$ $200$ $2\times 10^5$
$7\sim 8$ $200$ $10^9$ A
$9\sim 10$ $200$ $10^9$

特殊限制 A:所有点构成一条链, 编号为 $i$ 的点和编号为 $i + 1$ 的点之间有连边。

评分方式

本题共 $10$ 个测试点,每个测试点 $10$ 分。其中回答正确第一问可得 $7$ 分,回答正确第二问可得 $3$ 分。

时间限制:$\require{cancel}\cancel{2\texttt{s}}3\texttt{s}$

空间限制:$512\texttt{MB}$