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
上一篇: MongoDB如何查询耗时记录的方法详解
下一篇: Redis数据过期策略的实现详解