Codeforces Round #277 Div2 pD Valid Sets

給一個樹，每個點都有點權。
然後定義好的連通塊是(max(權重)-min(權重) <= d)
給d，問有多少個好的連通塊

dfs+好好記錄

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define P 1000000007
using namespace std;
typedef long long int int64;
int arr[100004];
set<int> bla[100004];
vector<int> to[100004];
int64 dfs(int fat, int prc, int _max, int _min, int main_id){
    //printf("dfs %d->%d\n", fat, prc);
    int64 cnt = 1LL;
    for(int lx = 0;lx < to[prc].size();lx++){
        int pind = to[prc][lx];
        if(pind == fat) continue;
        if(arr[pind] > _max) continue;
        if(arr[pind] < _min) continue;
        if(arr[pind] == _max){
            if(bla[pind].count(main_id))
                continue;
            else{
                bla[main_id].insert(pind);
                //bla[pind].insert(m);
            }
        }
        cnt *= dfs(prc, pind, _max, _min, main_id);
        cnt = cnt%P;
    }
    return (cnt+1LL)%P;
}
int main()
{
    int d, n; scanf("%d %d", &d, &n);

    for(int lx = 0;lx < n;lx++){
        scanf("%d", arr+lx);
    }
    for(int lx = 0;lx < n-1;lx++){
        int a, b; scanf("%d %d", &a, &b);
        to[a-1].push_back(b-1);
        to[b-1].push_back(a-1);
    }
    int64 cclemon = 0;
    for(int lx = 0;lx < n;lx++){
        cclemon += dfs(-1, lx, arr[lx], arr[lx]-d, lx);
        cclemon = (cclemon+P-1)%P;
    }
    printf("%I64d\n", cclemon);
    return 0;
}