Codeforces Round #277(Div. 2)Valid Sets 트리 DP

#include<iostream>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<vector>

#include<stdlib.h>

#include<algorithm>

using namespace std;

typedef long long LL;

LL d;

const LL maxn = 2222;

const LL mod = 1000000007;

struct Node

{

    LL next; LL to;

}e[maxn * 2];

LL len;

LL head[maxn];

LL dp[maxn];

LL father[maxn];

LL vis[maxn];



void add(LL from, LL to)

{

    e[len].to = to;

    e[len].next = head[from];

    head[from] = len++;

}



void build(LL root, LL pre)

{

    father[root] = pre;

    for (LL i = head[root]; i != -1; i = e[i].next){

        LL cc = e[i].to;

        if (cc == pre) continue;

        build(cc, root);

    }

}

LL val[maxn];



void dfs(LL x, LL root)

{

    dp[x] = 0; LL ans = 1;

    for (LL i = head[x]; i != -1; i = e[i].next){

        LL cc = e[i].to;

        if (cc == father[x])continue;

        if (val[cc] == val[root] && vis[cc]) continue;

        if (val[cc]<val[root] || val[cc] - val[root]>d) continue;

        //  prLLf("%I64d %I64d
",cc,val[cc]);system("pause");

        dfs(cc, root);

        ans *= dp[cc] + 1; ans %= mod;

    }

    dp[x] += ans; dp[x] %= mod;

}



int main()

{

    LL n;

    cin >> d >> n;

    len = 0;

    memset(head, -1, sizeof(head));

    memset(vis, 0, sizeof(vis));

    for (LL i = 1; i <= n; i++)

        scanf("%I64d", &val[i]);

    for (LL i = 1; i<n; i++){

        LL a; LL b;

        scanf("%I64d%I64d", &a, &b);

        add(a, b); add(b, a);

    }

    LL ans = 0;

    for (LL i = 1; i <= n; i++){

        build(i, i); dfs(i, i);

        ans += dp[i]; vis[i] = 1;

        ans %= mod;

        //  prLLf("%I64d
",dp[i]);

    }

    cout << ans << endl;

    return 0;

}