{"problem":{"name":"[省选联考 2022] 填树","description":{"content":"有一棵 $n$ 个节点的无根树，刚开始树上每个节点的权值均为 $0$。KK 想对这棵树进行一些修改，他会任选一个节点作为初始的当前节点，然后重复以下动作： 1. 将当前节点 $i$ 的权值修改为一个**正整数** $x$，需满足 $l_i \\leq x \\leq r_i$。其中 $l_i, r_i$ 是输入中给出的两个正整数。 2. 结束修改过程，或移动到一个与当前节点相邻的权值为 $0$ 的节","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8290"},"statements":[{"statement_type":"Markdown","content":"有一棵 $n$ 个节点的无根树，刚开始树上每个节点的权值均为 $0$。KK 想对这棵树进行一些修改，他会任选一个节点作为初始的当前节点，然后重复以下动作：\n\n1. 将当前节点 $i$ 的权值修改为一个**正整数** $x$，需满足 $l_i \\leq x \\leq r_i$。其中 $l_i, r_i$ 是输入中给出的两个正整数。\n2. 结束修改过程，或移动到一个与当前节点相邻的权值为 $0$ 的节点（如果不存在这样的节点，则必须结束修改过程）。\n\n现在 KK 有两个问题：\n\n1. 在修改结束后，可以得到多少棵不同的树，满足树上**非零权值**的最大值和最小值的差小于等于 $K$？其中 $K$ 是输入中给出的一个正整数。\n\n2. 这些满足条件的树的权值之和为多少？（树的权值定义为这棵树上所有节点的权值之和）\n\n你需要输出这两个问题的答案模 $10^9 + 7$。我们认为两棵树不同当且仅当至少存在一个节点的权值不同。\n\n温馨提示：\n\n1. KK 至少会修改一个节点（初始节点）。\n2. 实质上 KK 会修改树上的任意一条路径，最后需要满足这条路径上的点的权值最大值和最小值之差小于等于 $K$。\n\n## Input\n\n第一行两个正整数 $n, K$，表示节点数和权值差的最大值。\n\n接下来 $n$ 行，每行两个正整数 $l_i, r_i$，表示第 $i$ 个节点修改后权值的最小值和最大值。\n\n接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示节点 $u_i$ 和 $v_i$ 之间有一条边。数据保证形成一棵树。\n\n## Output\n\n输出两行，每行一个整数，分别表示第一问和第二问的答案模 $10^9 + 7$ 的值。注意，如果你不打算回答第二问，请在第二行任意输出一个整数。如果输出文件只有一行，则可能会因格式不符合要求被判 $0$ 分。\n\n[samples]\n\n## Background\n\n原题时限为 2s。\n\n## Note\n\n**【样例解释 #1】**\n\n| | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ |\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n| 节点 $1$ | $2$ | $3$ | $2$ | $3$ | $3$ | $3$ | $3$ | $3$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |\n| 节点 $2$ | $0$ | $0$ | $3$ | $3$ | $4$ | $0$ | $4$ | $3$ | $3$ | $4$ | $5$ | $0$ | $0$ | $0$ |\n| 节点 $3$ | $0$ | $0$ | $0$ | $0$ | $0$ | $4$ | $4$ | $4$ | $0$ | $0$ | $0$ | $4$ | $5$ | $6$ |\n\n表格中列出了全部 $14$ 棵满足条件的树，将这些树的权值加起来为 $78$。\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 200$，$1 \\leq l_i \\leq r_i \\leq {10}^9$，$1 \\leq K \\leq {10}^9$。\n\n| 测试点 | $n \\leq $ | $r_i, K \\leq$ | 其他限制 |\n|:-:|:-:|:-:|:-:|\n| $1$ | $5$ | $10$ | 无 |\n| $2$ | $30$ | $10^9$ | 无 |\n| $3$ | $30$ | $10^9$ | 无 |\n| $4$ | $30$ | $500$ | 无 |\n| $5$ | $200$ | $200000$ | 无 |\n| $6$ | $200$ | $200000$ | 无 |\n| $7$ | $200$ | $10^9$ | A |\n| $8$ | $200$ | $10^9$ | A |\n| $9$ | $200$ | $10^9$ | 无 |\n| $10$ | $200$ | $10^9$ | 无 |\n\n特殊限制 A：所有点构成一条链, 编号为 $i$ 的点和编号为 $i + 1$ 的点之间有连边\n\n**【评分方式】**\n\n本题共 $10$ 个测试点，每个测试点 $10$ 分。其中回答正确第一问可得 $7$ 分，回答正确第二问可得 $3$ 分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8290","tags":["数学","各省省选","2022","Special Judge","O2优化","树形 DP","拉格朗日插值法"],"sample_group":[["3 1\n2 3\n3 5\n4 6\n1 2\n1 3\n","14\n78\n"],["见附件中的 tree/tree2.in","见附件中的 tree/tree2.ans"],["见附件中的 tree/tree3.in","见附件中的 tree/tree3.ans"]],"created_at":"2026-03-03 11:09:25"}}