codeforces 486 D. Valid Sets（树形dp）

题目链接：http://codeforces.com/contest/486/problem/D

题意：给出n个点，还有n-1条边的信息，问这些点共能构成几棵满足要求的树，构成树的条件是。

1）首先这颗树非空。

2）这些点必须是联通的。

3）这棵树上最大的权值-最小的权值<=d。

题解：一道明显的树形dp，所以一半就设dp[i]表示以i为根的能构成几棵树。为了方便起见。就将i设为最大的那个点。如果遇到val值相同的话，就定义一

个方向，当val值相同时只能从下表大的点到下表小的点。dfs写法如下：

void dfs(int pos , int pre , int num) {

int len = vc[pos].size();

dp[pos] = 1;//每次递归到的点都要作为根节点所以权值先赋为1。

for(int i = 0 ; i < len ; i++) {

int u = vc[pos][i];

if(u == pre) continue;

　　//一下就是转移要满足的条件

if(a[num] < a[u]) continue;

if(a[num] - a[u] > d) continue;

if(a[num] == a[u] && num < u) continue;

dfs(u , pos , num);

dp[pos] = dp[pos] + dp[pos] * dp[u];

dp[pos] %= mod;

}

#include <iostream>

#include <cstring>

#include <vector>

#define mod 1000000007

using namespace std;

int a[2010] , d , n;

long long dp[2010];

vector<int>vc[2010];

void dfs(int pos , int pre , int num) {

    int len = vc[pos].size();

    dp[pos] = 1;

    for(int i = 0 ; i < len ; i++) {

        int u = vc[pos][i];

        if(u == pre) continue;

        if(a[num] < a[u]) continue;

        if(a[num] - a[u] > d) continue;

        if(a[num] == a[u] && num < u) continue;

        dfs(u , pos , num);

        dp[pos] = dp[pos] + dp[pos] * dp[u];

        dp[pos] %= mod;

    }

}

int main() {

    int u , v;

    cin >> d >> n;

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

        cin >> a[i];

    }

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

        cin >> u >> v;

        vc[u].push_back(v);

        vc[v].push_back(u);

    }

    long long ans = 0;

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

        dfs(i , 0 , i);

        ans += dp[i];

        ans %= mod;

    }

    cout << ans << endl;

    return 0;

}

巴特西

codeforces 486 D. Valid Sets（树形dp）

最新文章

热门文章