【【henuacm2016级暑期训练】动态规划专题 N】Valid Sets

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

给你一棵树。
让你统计其中子树T的数量。
这个子树T要满足最大值和最小值之差小于等于d

树形DP

可以枚举点root为子树的根。

统计以root为根的子树的个数。

根据每个儿子节点选或者不选。

如果选。则看看它是否满足以下条件:

权值小于等于根节点的权值。

(等于根节点的时候,要求该节点的标号<根节点的标号,不然会重复计数)

然后假设当前是枚举的第i个儿子

那么cnt表示的是这个根节点和前i-1个节点能形成的满足子树(是一个联通的整体)的个数。

那么如果选第i个儿子。

cnt = cnt + cntdp[son[i]];

这个cntdp[son[i]]表示前i-1个节点子树再加上第i个儿子的子树形成的满足子树的个数。然后再加上原先不包括第

i个儿子的方案(也即不选第i个子树的情形。就可以了。

难点在于想到枚举最大值这点。。

确定了最大值之后。就可通过比较差值来规划哪些点能够形成子树了。

很优秀。。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int N = 2000;

const LL MOD = 1e9+7;

int d,n,a[N+10];

vector<int> g[N+10];

LL ans = 0;

LL dfs(int x,int pre,int dominate){

    LL temp = 1;

    for (int y:g[x]){

        if (y==pre) continue;

        if (a[y]>a[dominate]) continue;

        if (a[y]==a[dominate] && y>dominate) continue;

        if (a[dominate]-a[y]>d) continue;

        temp = (temp + temp*dfs(y,x,dominate)%MOD)%MOD;

     }

    return temp;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> d >> n;

    for (int i = 1;i <= n;i++) cin >> a[i];

    for (int i = 1;i <= n-1;i++){

        int x,y;

        cin >> x >> y;

        g[x].push_back(y);g[y].push_back(x);

    }

    for (int i = 1;i <= n;i++){

        ans = (ans + dfs(i,-1,i))%MOD;

    }

    cout<<ans<<endl;

	return 0;

}