题解 CF486D Valid Sets

题目链接

相当牛逼。

这种找数量的题型，确定树形 \(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\) 为根节点的连通子图个数，转移是显然的：

代码：

#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;
}
/*
*/