CF486D Valid Sets

思路:比较妙的一个思路,考虑$dp(u)为点u作为最小的a_u情况下连通子图的数目$
为什么要这么做,因为最大-最小<=$d$这个约束十分麻烦,如果我们在枚举点的同时,认为它是作为集合中的最大/最小,就能不重复不遗漏地统计出合法的子图.
接下来就是dp过程，+1代表可以不选择该子树一种方案.$$dp(u)=\prod dp(v)+1$$
在dfs过程中,要特别注意$a[u]==a[v]$,事实上对于这两种点,得到的连通子图事实上有重复的部分。当以$u$为根的贡献算出来后,再次以$v$为根时,如果统计了$u$为根的子树,显然会造成重复部分的生成。因为这一部分已经在以$u$为根的时候被统计出来过一次了,这要求在dfs(v)的时候我们不能再次访问$u$节点.既然相同的点只能访问一次,不妨让数组编号小的访问大的.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
const int mod = INF;
vector<int> G[maxn];
int a[maxn];ll dp[maxn];int d,n;
void dfs(int u,int fa,int x){
	if(a[x]<a[u]||(a[x]==a[u]&&x<u)||(abs(a[u]-a[x])>d)) return ;
	dp[u] = 1;
	for(auto v : G[u]){
		if(v==fa) continue;
		dfs(v,u,x);
		dp[u] = 1LL*dp[u]*(dp[v]+1)%mod;
	}
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>d>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	ll ans = 0;
	for(int i=1;i<=n;i++){
		memset(dp,0,sizeof(dp));
		dfs(i,0,i);
		ans = (ans+dp[i])%mod;
	}
	cout<<ans<<"\n";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39