欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Codeforces486 D. Valid Sets(树形dp,去重技巧)

程序员文章站 2022-06-17 22:42:19
题意:给定n个点的树,每个点有点权a(i),给定整数D,定义合法连通块为:连通块中最大点权-连通块中最小点权<=D问有多少种合法连通块,答案对1e9+7取模数据范围:n<=2000,a(i)<=2000解法:容易想到枚举每个点作为连通块的点权最小值,且作为树的根,然后进行树形dp令d[i]为点i的方案数,根据乘法原理:d[x]=d[x]*(d[v]+1),(转移需要满足点权在合法范围内)复杂度O(n2)但是会有重复的情况:如果a(p1)=x,a(p2)=x,以p1为...

题意:

给定n个点的树,每个点有点权a(i),
给定整数D,
定义合法连通块为:
连通块中最大点权-连通块中最小点权<=D

问有多少种合法连通块,答案对1e9+7取模

数据范围:n<=2000,a(i)<=2000

解法:

容易想到枚举每个点作为连通块的点权最小值,且作为树的根,然后进行树形dp
令d[i]为点i的方案数,根据乘法原理:d[x]=d[x]*(d[v]+1),(转移需要满足点权在合法范围内)
复杂度O(n2)

但是会有重复的情况:
如果a(p1)=x,a(p2)=x,以p1为根的的时候dp到了p2,那么以p2为根的时候也会dp到p1,
这样就重复了,
解决方法:
当出现点v与当前根rt的点权相同的时候,规定一个唯一方向,例如:
当出现a(v)=a(rt)的时候,只有当rt>v的时候(这里比较的是编号大小),才能进行dp
这样能保证只dp一次,巧妙的去重了。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e3+5;
const int mod=1e9+7;
vector<int>g[maxm];
int a[maxm];
int D,n;
//
int d[maxm];
int L,R;
int rt;
void dfs(int x,int fa){
    d[x]=1;
    for(int v:g[x]){
        if(v==fa||a[v]<L||a[v]>R)continue;
        if(a[v]==a[rt]){
            if(v>rt)continue;
        }
        dfs(v,x);
        d[x]=d[x]*(d[v]+1)%mod;
    }
}
//
signed main(){
    ios::sync_with_stdio(0);
    cin>>D>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans=0;
    for(int i=1;i<=n;i++){//枚举每个点作为连通块点权最小值
        L=a[i],R=a[i]+D;
        rt=i;
        dfs(i,i);
        ans=(ans+d[i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}

本文地址:https://blog.csdn.net/weixin_44178736/article/details/107936536