CF486D 题解

题目传送门

题目分析

不算很难的树形 \(\text{dp}\)。

令 \(dp_i\) 表示以 \(i\) 为根的子树中联通子图的个数。

在更新的时候，考虑儿子的联通子图和自己的，则有：

选根的时候将 \(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);
}