相当牛逼。
这种找数量的题型，确定树形 \(dp\) 没跑了。
首先思考常规树形 \(dp\)，不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内（包括点 \(u\)），最大值是 \(a\)，最小值是 \(b\) 的连通子图数量，转移很容易，但是这样时间空间复杂度是 \(\rm O(n^3)\)，而且无论是状态上还是转移上都没有优化的空间。
这时考虑树形 \(dp\) 的另一种形式：特殊意义法。
我们从思考每个点对答案做出的贡献，从一个点出发，并规定这个点是联通子图中的最大值，为了不重复，规定若 \(a_x=a_y\)，当 \(x>y\) 时点 \(x\) 更大。
那么我们从每个点出发，设 \(f_u\) 表示以 \(u\) 为根节点的连通子图个数，转移是显然的：
\[f_{u}=f_{u}+f_{u}\times f_{son}
\]
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=2100;
const LL MOD=1e9+7;
int n,d;
int a[N];
LL f[N];
vector<int> g[N];
void dfs(int nd,int fa,int id,int w) {
f[nd]=1;
for(int x:g[nd]) {
if(x==fa) continue;
if(a[x]>w||(a[x]==w&&x>id)) continue;
if(w-a[x]>d) continue;
dfs(x,nd,id,w);
f[nd]=(f[nd]+f[nd]*f[x]%MOD)%MOD;
}
}
int main() {
cin>>d>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++) {
int x,y; cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
LL ans=0;
for(int i=1;i<=n;i++) {
memset(f,0,sizeof(f));
dfs(i,0,i,a[i]);
ans=(ans+f[i])%MOD;
}
cout<<ans;
return 0;
}
/*
*/