2023.7.20 闲话

每次模拟赛都证明我被所有人薄纱。

题意：给定 $n$ 个点的树，每个点有点权 $a_i$，求本质不同的连通块个数，满足连通块中最大点权减去最小点权恰为 $k$。

$n\lt 3400$，$0\leq a_i,k\leq n$。

题解：

直接考虑最大值与最小值之差恰为 $k$ 难以处理，可以先计算 $\leq k$ 的答案，减去 $\leq k-1$ 的答案即为 $=k$ 的答案。

树形 dp。令 $f(i)$ 为以 $i$ 为根的子树中钦定 $a_i$ 为最大值且极差 $\leq k$ 的答案。转移方程为

$f(i)=\prod\limits_{j\in son_i} f(j)+1$

枚举每个点作为整棵树的根节点，分别做一遍 dp。

再考虑，对于点权相同的两个点，可能会把一个连通块统计多次。只需要规定若点权相同则只在编号较小的点作为根时计算答案就能解决这个问题。

时间复杂度 $\mathcal{O}(n^2)$。

代码：

void dfs(int u, int fa, int be, int lim) {
    f[u] = 1;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        if (a[be] >= a[v] && a[be] - a[v] <= lim && (be < v || a[be] != a[v])) {
            dfs(v, u, be, lim);
            f[u] = 1ll * f[u] * (f[v] + 1) % mod;
        }
    }
}

// 主函数求解部分
for (int i = 1; i <= n; i++) {
    dfs(i, -1, i, k);
    ans1 = (ans1 + f[i]) % mod;
    if (k) {
        dfs(i, -1, i, k - 1);
        ans2 = (ans2 + f[i]) % mod;
    }
}
printf("%d\n", ((ans1 - ans2) % mod + mod) % mod);