【统一省选2022】填树 - 题目 - Universal Online Judge

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

将当前节点 $i$ 的权值修改为一个正整数 $x$ ，需满足 $l_{i} \leq x \leq r_{i}$ 。其中 $l_{i}, r_{i}$ 是输入中给出的两个正整数。
结束修改过程，或移动到一个与当前节点相邻的权值为 $0$ 的节点（如果不存在这样的节点，则必须结束修改过程）。

现在 KK 有两个问题：

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

温馨提示：

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

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

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

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

14
78

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

见附件下载。

对于 $100 %$ 的数据， $1 \leq n \leq 200, 1 \leq l_{i} \leq r_{i} \leq 10^{9}, 1 \leq K \leq 10^{9}$ 。

测试点	$n \leq$	$r_{i}, K \leq$	其他限制
$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$ 分。

时间限制： $2 s 3 s$

空间限制： $512 MB$

Universal Online Judge