一、题意理解

我们有一棵 $n$ 个节点的树，要给每个节点分配一个 $[1,m]$ 的整数权值，要求对于每条边 $(u,v)$，有 $|x_u - x_v| \ge k$。

求合法的染色方案数，对 $10^9+7$ 取模。

---

二、初步分析

这是一个典型的图上染色计数问题，但约束是相邻节点数值差至少为 $k$，而不是传统的不同颜色。

• 当 $k=0$ 时，约束不存在，方案数 = $m^n$。
• 当 $k \ge m$ 时，除非 $m=1$ 且 $k=0$，否则无解？不对，$k \ge m$ 时，相邻节点数值差至少 $m$，而数值范围 $[1,m]$，差最大 $m-1$，所以只有 $m=1$ 且 $k=0$ 才可能，否则无解。但 $k \le 100$，$m$ 可能很大，所以 $k \ge m$ 不会出现（因为 $m \ge 1$ 且 $k \le 100$，$m$ 可能到 $10^9$，所以 $k$ 肯定小于 $m$）。

---

三、小数据做法（$m \le 100$）

对于 $n \le 100$，$m \le 100$，我们可以用树形 DP。

设 $dp[u][c]$ 表示以 $u$ 为根的子树，节点 $u$ 染颜色 $c$ 时，子树的方案数。

转移： $ dp[u][c] = \prod_{v \in \text{son}(u)} \sum_{c'=1,\, |c-c'|\ge k}^m dp[v][c'] $

初始化：叶子节点 $dp[u][c] = 1$。

答案： $\text{ans} = \sum_{c=1}^m dp[\text{root}][c]$

复杂度 $O(n m^2)$，在 $n,m \le 100$ 时可行。

---

四、$m$ 很大时的优化

当 $m$ 很大时，$m \le 10^9$，不能枚举颜色。

观察约束 $|x_u - x_v| \ge k$，即 $x_v \le x_u - k$ 或 $x_v \ge x_u + k$。

如果我们固定节点 $u$ 的颜色 $c$，那么 $v$ 的合法颜色是： $[1, c-k] \cup [c+k, m]$ 注意边界处理。

---

1. 关键观察

对于固定的 $c$，$v$ 的合法颜色数量只与 $c$ 有关，并且是分段常数函数。

设 $f(c) =$ 从 $v$ 的合法颜色数量（即 $\sum_{c'} [|c-c'|\ge k]$）。

计算：

• 若 $c \le k$，则 $[c+k, m]$ 长度 $m-(c+k)+1 = m-c-k+1$，且 $[1, c-k]$ 为空（因为 $c-k \le 0$），所以 $f(c) = m-c-k+1$。
• 若 $k < c \le m-k$，则 $[1, c-k]$ 长度 $c-k$，$[c+k, m]$ 长度 $m-c-k+1$，所以 $f(c) = (c-k) + (m-c-k+1) = m-2k+1$。
• 若 $c > m-k$，则 $[c+k, m]$ 为空，$[1, c-k]$ 长度 $c-k$，所以 $f(c) = c-k$。

所以： $ f(c) = \begin{cases} m-c-k+1, & 1 \le c \le k \\ m-2k+1, & k < c \le m-k \\ c-k, & m-k < c \le m \end{cases} $

---

2. 利用函数的分段性质

在树形 DP 中，$dp[u]$ 可以看作一个定义在 $[1,m]$ 上的函数，值是一个整数（方案数）。

转移是： $ dp[u](c) = \prod_{v \in \text{son}(u)} \left( \sum_{c' \in \text{valid}(c)} dp[v](c') \right) $ 其中 $\text{valid}(c) = [1, c-k] \cup [c+k, m]$。

---

3. 区间和优化

我们只需要维护每个 $dp[u]$ 的前缀和 $S_u(x) = \sum_{i=1}^x dp[u](i)$。

那么： $\sum_{c' \in [1, c-k]} dp[v](c') = S_v(c-k)$ $ \sum_{c' \in [c+k, m]} dp[v](c') = S_v(m) - S_v(c+k-1) $ 所以： $ \sum_{c' \in \text{valid}(c)} dp[v](c') = S_v(c-k) + S_v(m) - S_v(c+k-1) $

于是转移可以写成： $ dp[u](c) = \prod_{v \in \text{son}(u)} \big[ S_v(c-k) + S_v(m) - S_v(c+k-1) \big] $

---

4. 关键点压缩

虽然 $m$ 很大，但 $n \le 100$，$k \le 100$，所以 $dp[u](c)$ 是分段多项式（每段是常数或线性函数），并且段的分界点只与 $k$ 有关。

事实上，$dp[u](c)$ 在 $c$ 的不同区间上是低次多项式（次数不超过子树大小）。

我们可以只计算 $dp[u]$ 在 $O(nk)$ 个关键点上的值，然后插值得到整段的值。

---

更简单的方法：注意到 $dp[u](c)$ 在区间 $[k+1, m-k]$ 上是常数（因为 $f(c)$ 是常数），在两端是线性函数。

所以我们可以只计算：

• $c = 1, 2, \dots, 2k$
• $c = m-2k+1, \dots, m$（如果 $m$ 很大，这部分可以用一个偏移量表示）

但 $m$ 可能很大，我们无法存下所有 $c$，但我们可以用生成函数或多项式来表示 $dp[u]$。

---

5. 多项式方法

设 $F_u(x) = \sum_{c=1}^m dp[u](c) x^{c}$ 是生成函数。

转移： $ F_u(x) = \sum_{c=1}^m \left[ \prod_{v} \big( S_v(c-k) + S_v(m) - S_v(c+k-1) \big) \right] x^{c} $ 这看起来复杂，但 $S_v(c) = [x^{1..c}] F_v(x)$ 是前缀和。

实际上更简单：我们只关心 $S_v(m)$ 和 $S_v$ 在 $O(k)$ 个位置的值。

---

6. 离散化关键点

由于 $n$ 小 $k$ 小，$dp[u](c)$ 在 $c \in [1, 2k] \cup [m-2k, m]$ 之外是常数，所以我们可以只计算 $O(k)$ 个 $c$ 的值，然后乘以区间长度。

具体：

• 对 $c = 1..2k$ 直接计算。
• 对 $c = m-2k+1..m$ 直接计算（如果 $m$ 很大，这部分可以用 $c' = m-c$ 对称处理）。
• 中间大段 $[2k+1, m-2k]$ 上 $dp[u](c)$ 是常数，记为 $V$，这段长度 $L = m - 4k$（如果 $m > 4k$），贡献 $V \cdot L$。

这样我们只需计算 $O(k)$ 个点的 $dp$ 值，复杂度 $O(n k^2)$。

---

五、算法步骤（对大数据）

1. 如果 $m \le 4k$，直接枚举所有 $c$ 做树形 DP。
2. 否则：
   • 对每个节点 $u$，维护两个数组 $low[1..2k]$ 和 $high[1..2k]$，分别表示 $c=1..2k$ 和 $c=m-2k+1..m$ 时的 $dp[u](c)$，以及一个常数 $mid$ 表示中间段的 $dp[u](c)$。
   • 转移时，对每个 $c$ 计算 $\prod_{v} (S_v(c-k) + S_v(m) - S_v(c+k-1))$，其中 $S_v(x)$ 用 $low, mid, high$ 计算：
     • 如果 $x \le 2k$，$S_v(x) = \sum_{i=1}^x low[i]$。
     • 如果 $2k < x \le m-2k$，$S_v(x) = S_v(2k) + mid \cdot (x - 2k)$。
     • 如果 $x > m-2k$，$S_v(x) = S_v(m-2k) + \sum_{i=m-2k+1}^x high[i - (m-2k)]$。
   • 注意 $S_v(m)$ 是总方案数。
3. 最终答案是 $S_{\text{root}}(m)$。

---

六、代码框架（C++）

这里给出 $m \le 100$ 的直接 DP 实现（适用于测试点 1,2）：

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <array>

using namespace std;

array<array<long long, 20001>, 101>   DParr;
array<vector<int>, 101>              tree;
array<long long, 101>                answers;
const int                           moder = 1e9 + 7;

inline long long rgsum(int curnd, int rgl, int rgr) {
    if (rgl > rgr)
        return 0;

    if (rgl < 1)
        rgl = 1;

    return (DParr[curnd][rgr] - DParr[curnd][rgl - 1] + moder) % moder;
}

void DFS_dp(int curnd, int father, const int mind, const int maxv) {
    DParr[curnd].fill(0);

    for (int i = 1; i <= min(20000, maxv); i++)
        DParr[curnd][i] = 1;

    for (int i : tree[curnd]) {
        if (i == father)
            continue;

        DFS_dp(i, curnd, mind, maxv);

        if (maxv <= 19900)
            for (int j = 1; j <= 19900; j++)
                (DParr[curnd][j] *= answers[i] - rgsum(i, j - mind + 1, j + mind - 1) + moder) %= moder;
        else {
            for (int j = 1; j <= 9901; j++)
                (DParr[curnd][j] *= answers[i] - rgsum(i, j - mind + 1, j + mind - 1) + moder) %= moder;

            for (int j = 9902; j <= 20000; j++)
                if (maxv - j + 1 > 9901)
                    DParr[curnd][j] = DParr[curnd][9901];
                else
                    DParr[curnd][j] = DParr[curnd][maxv - j + 1];
        }
    }

    for (int i = 1; i <= 20000; i++)
        (DParr[curnd][i] += DParr[curnd][i - 1]) %= moder;

    if (maxv <= 20000)
        answers[curnd] = DParr[curnd][20000] % moder;
    else
        answers[curnd] = (DParr[curnd][9900] * 2 + (maxv - 19800) * (DParr[curnd][9901] - DParr[curnd][9900] + moder)
                          % moder) % moder;
}

int main(int argc, char *argv[], char *envp[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testcnt;
    cin >> testcnt;

    while (testcnt--) {
        for (int i = 1; i <= 100; i++)
            tree[i].clear();

        int cnt, mind, maxv;
        cin >> cnt >> maxv >> mind;

        for (int i = 1; i < cnt; i++) {
            int node1, node2;
            cin >> node1 >> node2;
            tree[node1].push_back(node2), tree[node2].push_back(node1);
        }

        DFS_dp(1, 0, mind, maxv);
        cout << answers[1] << '\n';
    }

    return 0;
}

---

七、总结

本题的关键在于：

1. 理解相邻节点数值差约束的树形染色计数。
2. 对小 $m$ 直接树形 DP。
3. 对大 $m$ 利用 $dp[u](c)$ 的分段常数/线性性质，压缩状态数。
4. 通过维护前缀和快速计算转移。