JZOJ 5913. 林下风气
2024-08-25 12:43:33
Description
里口福因有林下风气,带领全国各地高校掀起了一股AK风,大家都十分痴迷于AK。里口福为了打击大家的自信心,出了一道自以为十分困难的题目。
里口福有一棵树,第i个节点上有点权ai,他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差=k,两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于AK的你马上接下这道题目,在里口福狂妄的笑声中,你切掉这道题的决心更加坚定了,现在就差你的代码了。
里口福有一棵树,第i个节点上有点权ai,他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差=k,两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于AK的你马上接下这道题目,在里口福狂妄的笑声中,你切掉这道题的决心更加坚定了,现在就差你的代码了。
Input
第一行两个整数n,k,表示树的大小以及题目中的k。
第二行n个整数,第i个整数表示ai。
接下来n-1行,每行两个整数x,y表示树边(x,y)。
第二行n个整数,第i个整数表示ai。
接下来n-1行,每行两个整数x,y表示树边(x,y)。
Output
一行一个整数,表示答案,答案对19260817取模。
Sample Input
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
Sample Output
4
Data Constraint
对于30%的数据,n<=22
对于另外20%的数据,树是一条链
对于另外20%的数据,ai只有0和1两种
对于100%的数据,N<=3333,0<=ai<=N,K>=0
对于另外20%的数据,树是一条链
对于另外20%的数据,ai只有0和1两种
对于100%的数据,N<=3333,0<=ai<=N,K>=0
做法:有一个套路,所有差值<=k的联通块减去<=k-1的联通块即是答案,可以用树形dp统计。
#include <cstdio>
#include <iostream>
#include <cstring>
#define mo 19260817
#define N 7777
#define LL long long
using namespace std;
int n,m,ls[N],tot;
LL ans,ans2;
struct edge{
int to,next;
}e[N]; struct arr{
int s,num;
}a[N]; void add(int x,int y){
e[++tot].to=y;
e[tot].next=ls[x];
ls[x]=tot;
} void Init(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i].s),a[i].num=i;
for (int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
} LL count(int x,int pre,int root){
LL sum=;
for (int i=ls[x];i;i=e[i].next){
int v=e[i].to;
if (v==pre) continue;
if (a[root].s-a[v].s>m||a[root].s<a[v].s) continue;
if (a[root].s==a[v].s&&a[root].num<a[v].num) continue;
sum=(sum*(count(v,x,root)+))%mo;
}
return sum;
} LL count2(int x,int pre,int root){
LL sum=;
for (int i=ls[x];i;i=e[i].next){
int v=e[i].to;
if (v==pre) continue;
if (a[root].s-a[v].s>m-||a[root].s<a[v].s) continue;
if (a[root].s==a[v].s&&a[root].num<a[v].num) continue;
sum=(sum*(count2(v,x,root)+))%mo;
}
return sum;
} int main(){
freopen("lkf.in","r",stdin);
freopen("lkf.out","w",stdout);
Init();
for (int i=;i<=n;i++)
ans=(ans+count(i,,i))%mo;
if (m!=){
for (int i=;i<=n;i++)
ans2=(ans2+count2(i,,i))%mo;
}
cout<<(ans-ans2+mo)%mo;
}
最新文章
- 配置本机IIS服务器
- centos 7 64位虚机上android4环境运行
- Openstack python api 学习文档 api创建虚拟机
- loadrunner中创建唯一随机数
- Codeforces Educational Codeforces Round 15 A. Maximum Increase
- WindowsPhone 8 开发 之 本地数据库应用
- 查看SQLServer数据库信息的SQL语句
- java 显示视频时间--玩的
- react - web + webpack4 从0构建
- CSS其它特性
- 使用Nodpad++正则替换
- JS脚本-零星片段
- centos6.7环境之kvm虚拟化quem工具配置及使用详解
- 爬取猫眼电影TOP100
- 【Linux】shell编程案例
- C# GetType和typeof的区别
- python 获取excel文件内sheet名称列表
- dubbo异步调用三种方式
- 项目评审ppt的纲要
- Windows网络配置脚本