CF round 277 (div2) D题 树形dp

题意：

题目链接：http://codeforces.com/contest/486/problem/D
找到树中有多少个满足条件的集合，保证联通且集合中最大值与最小值的差不超过d

---

思路：

这种最大值与最小值的差有范围的情况，要先固定一端，比如枚举最大值，然后找每个节点充当最大值能满足的集合有多少。
这样的思路会存在多个最大值的重复问题，需要对dfs限定顺序，比如只允许相同最大值只允许从小的访问大的。

---

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int MAXN = 2005;

int now, d, n, num;
int dp[MAXN], a[MAXN];
vector <int> tree[MAXN];

LL dfs(int u, int pa) {
    int cnt = tree[u].size();
    LL res = 1;
    for (int i = 0; i < cnt; i++) {
        int v = tree[u][i];
        if (v == pa) continue;
        if (a[v] < a[now] - d || a[v] > a[now]) continue;
        if (a[v] == a[now] && v > now) continue;
        res = res * ((dfs(v, u) + 1LL) % MOD) % MOD;
    }
    dp[u] = res;
    return res;
}

LL solve() {
    LL ans = 0;
    for (int u = 1; u <= n; u++) {
        now = u;
        memset(dp, 0, sizeof(dp));
        ans = (ans + dfs(u, -1)) % MOD;
    }
    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &d, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        tree[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    printf("%I64d\n", solve());
    return 0;
}