JZOJ-senior-5913. 【NOIP2018模拟10.19】林下风气

Time Limits: 2000 ms Memory Limits: 524288 KB

Description

里口福因有林下风气，带领全国各地高校掀起了一股AK风，大家都十分痴迷于AK。里口福为了打击大家的自信心，出了一道自以为十分困难的题目。
里口福有一棵树，第i个节点上有点权ai，他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差=k，两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于AK的你马上接下这道题目，在里口福狂妄的笑声中，你切掉这道题的决心更加坚定了，现在就差你的代码了。

Input

第一行两个整数n,k，表示树的大小以及题目中的k。
第二行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

Solution

Algorithm 1

2 N 2^N 2N 枚举每个点选与不选，再暴力判断是否联通，符合题目要求即可。
期望得分 $30$

Algorithm 2

直接输出0/1或其他好数字，即可获得意想不到的分数。
期望得分 $10$ 到 $30$ 不等

Algorithm 3

一条链，连通块肯定为一段区间，那么枚举左右端点，记录最大最小值即可。
期望得分 $20$

Algorithm 4

当 $a[i]$ 非0即1时，易知仅 $k=0/1$ 时答案部位0。若 $k==0$ 那么算出所有点权相同的连通块个数即可；若 $k==1$，总数减去不合法的就可以了。
期望得分 $20$

Algorithm 5

考虑树形 $dp$，将一个可行的连通块的贡献记在该连通块深度最小的点上，这样便可以做到不重不漏。
枚举合法连通块的最小值，那么便有唯一的最大值与之对应。设 $f[i][0/1][0/1]$表示从以 $i$ 为根的子树中选出包含 $i$ 的连通块 ，最小值和最大值是否出现的连通块的数量，枚举后两维的状态暴力转移即可，注意判断不可行的情况。
期望得分 $100$

Algorithm 6

枚举 $i$ 号节点为根，记为 $rt$ ，并强制其为连通块的最小值，那么最大值即为 $a[rt]+k$，仍然考虑树形 $dp$ ，$f[x][0/1]$ 表示以 $x$ 为根的连通块中，是否出现过最大值的方案数，转移方程详见代码。
期望得分 $100$

Code

#include
#include#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long longusing namespace std;const int N=3350,P=19260817;
int n,k,rt,num;
int a[N],last[N];
ll f[N][2],ans;
struct edge{int to,next;}e[2*N];void add(int x,int y)
{e[++num]=(edge){y,last[x]},last[x]=num;
}void dfs(int x,int fa)
{if(a[x]==a[rt]+k) f[x][1]=1,f[x][0]=0; else f[x][1]=0,f[x][0]=1;for(int w=last[x];w;w=e[w].next){int y=e[w].to;if(y==fa||a[y]==a[rt]&&y>rt||a[y]<a[rt]||a[y]>a[rt]+k) continue;dfs(y,x);f[x][1]=(f[x][1]+f[x][1]*f[y][0]%P+f[x][0]*f[y][1]%P+f[x][1]*f[y][1]%P)%P;f[x][0]=(f[x][0]+f[x][0]*f[y][0]%P)%P;}
}int main()
{freopen("lkf.in","r",stdin);freopen("lkf.out","w",stdout);scanf("%d%d",&n,&k);fo(i,1,n) scanf("%d",&a[i]);fo(i,1,n-1){int x,y;scanf("%d%d",&x,&y);add(x,y),add(y,x);}fo(i,1,n) rt=i,dfs(rt,0),ans=(ans+f[i][1])%P;printf("%lld",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！