CF 486D Valid Sets

题目描述

https://codeforces.com/problemset/problem/486/D?f0a28=1

Solution

注意到 $n\le 2000$，这启示我们可以考虑 $O(n^2)$ 的算法

对于连通块计数问题，我们首先要考虑一个合法的连通块我们要如何统计他的贡献

在这道题中，我们自然能够想到以一个连通块的最大值为根来统计这个连通块的贡献

确定最大值之后最小值也确定了，那么我们可以直接令 $f[u]$ 表示 $u$ 内的连通块数量，以每个点为根跑一树形 $dp$ 即可

时间复杂度 $O(n^2)$

#include <iostream>
#define maxn 2010
using namespace std;

const int p = 1000000007;

int n, a[maxn], d;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dfs(int u, int fa, int o) {
    if (a[u] < a[o] - d || a[u] > a[o] || a[u] == a[o] && u > o) return 0;
    int ans = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        ans = 1ll * ans * (dfs(v, u, o) + 1) % p;
    }
    return ans;
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> d >> n; int ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } 
    for (int i = 1; i <= n; ++i)
        ans = (ans + dfs(i, 0, i)) % p;
    cout << ans << "\n"; 
    return 0;
}