codeforces 486D D. Valid Sets(树形dp)

87 阅读 0 评论 58 点赞

我是靠谱客的博主端庄菠萝，最近开发中收集的这篇文章主要介绍codeforces 486D D. Valid Sets(树形dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

codeforces 486D

题目大意：

给出一棵树，求这棵树的满足最大点与最小点之差小于d的连通子图的个数。

题目分析：

因为涉及到图中的最大点和最小点，所以我们先枚举一个点作为最大点，然后搜比它小的与它连通的点进行dp
对于每个与它相邻不比它大的点有两种情况，不选这个点的话，那么只有一种情况，因为所选的子图必须是连通的，如果不选这个点，那么它的子树中的点都不选，如果选这个点，那么递归地考虑。
只是要考虑两个点相等的情况可能会导致重复计算，所以我们将相同权值的点之间定义方向，比如标号小的点能够走到标号大的点，相反则不行，这样就能保证我们对每个情况不会重复计算了。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAX 2007

using namespace std;

typedef long long LL;

int n,d,a[MAX];
const LL mod = 1e9+7;
vector<int> e[MAX];
LL dp[MAX];
bool used[MAX];

void Clear ( )
{
    for ( int i = 0 ; i < MAX ; i++ )
        e[i].clear();
}

void add ( int u , int v )
{
    e[u].push_back ( v );
    e[v].push_back ( u );
}

void dfs ( int u , int p , int x )
{
    dp[u] = 1;
    for ( int i = 0 ; i < e[u].size() ; i++ )
    {
        int v = e[u][i];
        if ( v == p ) continue;
        if ( a[v] > a[x] ) continue;
        if ( a[v] < max(0,a[x]-d) ) continue;
        if ( a[v] == a[x] && v < x ) continue; 
        dfs ( v , u , x );
        dp[u] *= dp[v]+1LL;
        dp[u] %= mod;
    }
}

int main ( )
{
    while ( ~scanf ( "%d%d" , &d , &n ) )
    {
        Clear();
        for ( int i = 1 ; i <= n ; i++ )
            scanf ( "%d" , &a[i] );
        for ( int i = 1 ; i < n ; i++ )
        {
            int x,y;
            scanf ( "%d%d" , &x , &y );
            add ( x , y );
        }
        LL ans = 0;
        memset ( used , 0 , sizeof ( used ) );
        for ( int i = 1 ; i <= n ; i++ )
        {
            dfs ( i , -1 , i );
            ans += dp[i];
            ans %= mod;
        }
        printf ( "%lldn" , ans );
    }
}