#PQJ926x4050. QOJ 926_4050

    ID: 3061 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2022 统一省选动态规划深搜

QOJ 926_4050

NOI2022 省选 DAY1 填树(tree) 填树(tree) 【题目描述】 有一棵n 个节点的无根树,刚开始树上每个节点的权值均为0。KK 想对这棵树进 行一些修改,他会任选一个节点作为初始的当前节点,然后重复以下动作:

  1. 将当前节点i 的权值修改为一个.正.整.数x,需满足li ≤x ≤ri。其中li, ri 是输入 中给出的两个正整数。
  2. 结束修改过程,或移动到一个与当前节点相邻的权值为0 的节点(如果不存在这 样的节点,则必须结束修改过程)。 现在KK 有两个问题:
  3. 在修改结束后,可以得到多少棵不同的树,满足树上.非.零.权.值的最大值和最小值 的差小于等于K?其中K 是输入中给出的一个正整数。
  4. 这些满足条件的树的权值之和为多少?(树的权值定义为这棵树上所有节点的权 值之和) 你需要输出这两个问题的答案模109 + 7。我们认为两棵树不同当且仅当至少存在 一个节点的权值不同。 温馨提示:
  5. KK 至少会修改一个节点(初始节点)。
  6. 实质上KK 会修改树上的任意一条路径,最后需要满足这条路径上的点的权值最 大值和最小值之差小于等于K。 【输入格式】 从文件tree.in 中读入数据。 第一行两个正整数n, K,表示节点数和权值差的最大值。 接下来n 行,每行两个正整数li, ri,表示第i 个节点修改后权值的最小值和最大 值。 接下来n −1 行,每行两个正整数ui, vi,表示节点ui 和vi 之间有一条边。数据保 证形成一棵树。 【输出格式】 输出到文件tree.out 中。 输出两行,每行一个整数,分别表示第一问和第二问的答案模109 + 7 的值。注意, 如果你不打算回答第二问,请在第二行任意输出一个整数。如果输出文件只有一行,则 会因格式不符合要求被判0 分。 第6 页 共14 页

NOI2022 省选 DAY1 填树(tree) 【样例1 输入】 1 3 1 2 2 3 3 3 5 4 4 6 5 1 2 6 1 3 【样例1 输出】 1 14 2 78 【样例1 解释】 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。 【样例2】 见选手目录下的tree/tree2.in 与tree/tree2.ans。 【样例3】 见选手目录下的tree/tree3.in 与tree/tree3.ans。 【数据范围】 对于100% 的数据,1 ≤n ≤200, 1 ≤li ≤ri ≤109, 1 ≤K ≤109。 第7 页 共14 页

NOI2022 省选 DAY1 填树(tree) 测试点 n ≤ ri, K ≤ 其他限制 1 5 10 无 2 ∼3 30 109 4 500 5 ∼6 200 200000 7 ∼8 109 A 9 ∼10 无 特殊限制A:所有点构成一条链, 编号为i 的点和编号为i + 1 的点之间有连边 【评分方式】 本题共10 个测试点,每个测试点10 分。其中回答正确第一问可得7 分,回答正确 第二问可得3 分。 第8 页 共14 页