问题重述

我们有一棵 $n$ 个节点的树，每个节点 $i$ 有权值范围 $[l_i, r_i]$。KK 的操作相当于选择树上的一条简单路径（长度至少为 1），给路径上的每个节点分配权值（在对应范围内），其他节点权值为 0。

要求：路径上节点权值的最大值与最小值之差 $\le K$。

需要计算：

1. 满足条件的方案数
2. 所有满足条件的方案的权值总和

---

关键观察

1. 问题转化

由于操作规则（只能移动到权值为 0 的相邻节点），KK 修改的节点构成一条简单路径。

因此问题转化为：对树上的每条简单路径，计算满足条件的赋值方案。

2. 最大值最小值约束的处理

设路径上节点的权值集合为 $\{v_1, v_2, \dots, v_m\}$，要求：

$$\max(v_i) - \min(v_i) \le K$$

一个常用技巧是：枚举最小值 $L$，那么所有权值必须在 $[L, L+K]$ 范围内。

3. 离散化

由于 $l_i, r_i, K$ 可达 $10^9$，但 $n \le 200$，我们可以将所有关键点（$l_i, r_i, l_i+K, r_i+K$ 等）离散化，将值域降到 $O(n)$ 级别。

---

核心解法

1. 容斥思想

对于固定的最小值下界 $L$，定义：

• $f(L)$：所有路径上节点权值都在 $[L, L+K]$ 内的方案数
• $g(L)$：所有路径上节点权值都在 $[L, L+K]$ 内的权值和

那么最终答案可以通过 $f(L), g(L)$ 的适当组合得到。

但直接计算 $f(L)$ 会重复计算，因为一个方案可能被多个 $L$ 统计。

2. 精确计数方法

更精确的方法是：对于每个路径和每个赋值方案，设其实际最小值为 $min$，最大值为 $max$，那么该方案会对所有满足 $L \le min$ 且 $L+K \ge max$ 的 $L$ 有贡献。

通过合适的差分技巧，可以避免重复计数。

---

算法框架

1. 离散化值域

收集所有关键点：

• $l_i, r_i$ 对于所有 $i$
• $l_i - K, r_i - K$（考虑最小值范围） 去重排序后得到离散化数组 $vals[1..M]$。

2. 枚举最小值区间

对于每个离散化区间 $[vals[i], vals[i+1])$，最小值 $L$ 在这个区间内时，每个节点 $u$ 的可用权值范围是：

$$[\max(l_u, L), \min(r_u, L+K)]$$

如果这个区间为空，则该节点不能出现在路径中。

3. 树上路径统计

对于固定的 $L$（实际上是一个区间），我们需要统计：

定义：

• $cnt[u]$：以 $u$ 为根的子树中，从 $u$ 开始向下的路径的方案数
• $sum[u]$：对应的权值和

转移： 对于节点 $u$，设其权值选择范围为 $[a_u, b_u]$，那么：

• 如果 $a_u > b_u$，则 $cnt[u] = 0, sum[u] = 0$
• 否则：
  • 单节点路径：$cnt[u] = b_u - a_u + 1$，$sum[u] = \frac{(a_u + b_u)(b_u - a_u + 1)}{2}$
  • 合并子节点 $v$：新路径数 = $cnt[u] \times cnt[v]$，新权值和 = $cnt[u] \times sum[v] + sum[u] \times cnt[v]$

但要注意：路径可以是任意的，不一定要从根开始。我们需要在 DP 过程中统计所有路径。

4. 统计所有路径

在树形 DP 时，对于每个节点 $u$，我们考虑：

• 单点路径
• $u$ 与每个子树的路径连接
• 不同子树之间的路径通过 $u$ 连接

这需要仔细设计合并顺序。

---

复杂度分析

• 离散化后值域大小 $M = O(n)$
• 对每个值域区间：$O(n)$ 的树形 DP
• 总复杂度：$O(n^3)$，对于 $n \le 200$ 可接受

---

难点与技巧

1. 路径统计的完整性

需要确保统计到所有简单路径，包括：

• 单点路径
• 从上到下的路径
• 跨越多个子树的路径

2. 权值和的维护

不仅要统计方案数，还要统计权值和。这需要在 DP 状态中同时维护：

• 路径数量
• 路径权值和

合并时使用组合数学公式。

3. 大值域处理

通过离散化，将 $10^9$ 的值域降到 $O(n)$，使得枚举最小值可行。

4. 边界情况

• 空区间的处理
• 模运算下的除法（需要乘法逆元）
• 路径至少包含一个节点

---

总结

这道题综合了：

1. 树形DP：统计树上所有路径信息
2. 离散化：处理大值域
3. 组合计数：方案数和权值和的维护
4. 容斥原理：处理最大值最小值约束

通过枚举最小值区间，将原问题转化为多个区间约束下的树上路径统计子问题，再利用树形DP高效求解，体现了"化繁为简"的解题思想。