题目分析
不算很难的树形 \(\text{dp}\)。
令 \(dp_i\) 表示以 \(i\) 为根的子树中联通子图的个数。
在更新的时候，考虑儿子的联通子图和自己的，则有：
\[dp_u = dp_u \times (dp_v + 1)
\]
选根的时候将 \(a\) 最大的作为根节点。还要注意另外一点，就是当 \(a_{fa}=a_{v}\) 时，双方互相都可以更新，所以会出现问题。此时将根节点设为编号大的那个即可。
贴上代码
#include<bits/stdc++.h>
#define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("Yes")
#define no puts("No")
#define inf 1e9
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=2e5+5;
const int mod=1e9+7;
int n,d;
int ans;
int a[maxn];
int dp[maxn];
int cnt_edge,head[maxn];
struct edge{
int to,nxt;
}e[maxn<<1];
void add(int u,int v){
e[++cnt_edge].nxt=head[u];
e[cnt_edge].to=v;
head[u]=cnt_edge;
}
void dfs(int u,int fa,int rt){
dp[u]=1;
for(register int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
if((a[v]==a[rt]&&v<rt)||(a[v]-a[rt]>d||a[rt]>a[v])) continue;
dfs(v,u,rt);
dp[u]*=dp[v]+1;dp[u]%=mod;
}
}
inline void init(){
d=read();n=read();
for(register int i=1;i<=n;++i) a[i]=read();
for(register int i=1;i<n;++i){
int u=read(),v=read();
add(u,v);add(v,u);
}
}
signed main(){
init();
for(register int i=1;i<=n;++i){
dfs(i,0,i);
ans+=dp[i];ans%=mod;
}
printf("%d",ans);
}