Description

题目链接

题目大意:求树上的满足点权最大值减最小值小于等于 $d$ 的连通块数量。$n \le 2000$。

Solution

盯着看了半天没看出来,一看题解被震撼了。

考虑树形 DP,枚举贡献最大值的点 $r$,同时满足编号最大,然后以 $r$ 为根开始 dfs。

设 $f(i)$ 表示以 $r$ 为最大值的点,子树 $i$ 中的连通块数量,枚举儿子 $j$,如果满足 $a_r > a_j$ 或 $a_r = a_j \land r > j$ 且 $a_r - a_j \le d$,就让 $f(i)$ 加上 $f(i) \times f(j)$。

不选 $j$ 子树的方案为 $f(i)$,选的方案为 $f(i) \times f(j)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

const LL mod = 1e9 + 7;

std::vector<int> g[2010];
LL f[2010];
LL ans;
int a[2010];
int n, d;

void dfs(int x, int p, int r) {
    f[x] = 1;
    for (auto i : g[x]) {
        if ((i != p) && ((a[r] > a[i] || a[r] == a[i] && r > i) && a[r] - a[i] <= d)) {
            dfs(i, x, r);
            f[x] += f[x] * f[i] % mod;
            f[x] %= mod;
        }
    }
}

int main() {
    read(d), read(n);
    for (int i = 1; i <= n; ++i)    read(a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)    dfs(i, 0, i), ans += f[i], ans %= mod;
    printf("%lld\n", ans);
    return 0;
}
Last modification:November 9th, 2021 at 01:12 am