Codeforces 735 E Ostap and Tree
Discription
Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph.
Ostap's tree now has n vertices. He wants to paint some vertices of the tree black such that from any vertex u there is at least one black vertex v at distance no more than k. Distance between two vertices of the tree is the minimum possible number of edges of the path between them.
As this number of ways to paint the tree can be large, Ostap wants you to compute it modulo 109 + 7. Two ways to paint the tree are considered different if there exists a vertex that is painted black in one way and is not painted in the other one.
Input
The first line of the input contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) — the number of vertices in Ostap's tree and the maximum allowed distance to the nearest black vertex. Don't miss the unusual constraint for k.
Each of the next n - 1 lines contain two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of vertices, connected by the i-th edge. It's guaranteed that given graph is a tree.
Output
Print one integer — the remainder of division of the number of ways to paint the tree by 1 000 000 007 (109 + 7).
Examples
2 0
1 2
1
2 1
1 2
3
4 1
1 2
2 3
3 4
9
7 2
1 2
2 3
1 4
4 5
1 6
6 7
91
Note
In the first sample, Ostap has to paint both vertices black.
In the second sample, it is enough to paint only one of two vertices, thus the answer is 3: Ostap can paint only vertex 1, only vertex 2, vertices 1 and 2 both.
In the third sample, the valid ways to paint vertices are: {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}.
状态定义见代码注释,注意合并两个子树的时候如果最近的黑点到根的距离>k那么就相当于没有黑点。
/*
f[x][y][z] => 以x为根的子树中 ,最近的黑点距离x为 y-1 ,
最远的(没有被覆盖到的)白点距离x为 z-1 的方案数。 如果不存在黑点或白点那么那一维是0
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1000000007;
const int maxn=105;
int hd[maxn],n,m,to[maxn*2],num;
int ne[maxn*2],f[maxn][25][25],k;
int ans=0,g[25][25]; inline int add(int x,int y){
x+=y;
return x>=ha?x-ha:x;
} inline void addline(int x,int y){
to[++num]=y,ne[num]=hd[x],hd[x]=num;
} inline void MERGE(int x,int y){
memset(g,0,sizeof(g)); for(int i=k+1;i>=0;i--)
for(int j=k+1;j>=0;j--) if(f[x][i][j])
for(int I=k+1,NearB,FarW;I>=0;I--)
for(int J=k+1;J>=0;J--) if(f[y][I][J]){
NearB=1<<30;
if(i) NearB=i;
if(I) NearB=min(NearB,I+1);
if(NearB>k+1) NearB=0; FarW=0;
if(j&&(!I||(j+I-1)>k)) FarW=j;
if(J&&(!i||(J+i-1)>k)) FarW=max(FarW,J+1); g[NearB][FarW]=add(g[NearB][FarW],f[x][i][j]*(ll)f[y][I][J]%ha);
} memcpy(f[x],g,sizeof(g));
} void dfs(int x,int fa){
f[x][1][0]=f[x][0][1]=1;
for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){
dfs(to[i],x);
MERGE(x,to[i]);
}
} inline void calc(){
for(int i=k+1;i>=0;i--) ans=add(ans,f[1][i][0]); /*
for(int i=1;i<=n;i++)
for(int j=0;j<=k+1;j++)
for(int l=0;l<=k+1;l++) printf("f[%d][%d][%d] = %d\n",i,j,l,f[i][j][l]);
*/
} int main(){
scanf("%d%d",&n,&k);
int uu,vv;
for(int i=1;i<n;i++){
scanf("%d%d",&uu,&vv);
addline(uu,vv),addline(vv,uu);
} dfs(1,1);
calc();
printf("%d\n",ans);
return 0;
}
最新文章
- django -model
- [转]IE8兼容Jquery.validate.js兼容问题
- Java开发之文件上传
- event.srcElement 用法笔记e.target
- ODBC 是什么
- [转]15 个顶级 HTML5 游戏引擎
- Codeforces739E Gosha is hunting
- SQL日期格式转换(经常用又经常忘记的东西)转载自http://www.cnblogs.com/wangyuelang0526/archive/2012/06/06/2538224.html
- quartz任务时间调度入门使用
- 前后端分离之vue2.0+webpack2 实战项目 -- webpack介绍
- 如何生成转储(dmp)文件--工具篇
- SpringMVC + Mybatis bug调试 SQL正确,查数据库却返回NULL
- 收集—— css实现垂直居中
- python闯关之路(五)前端开发
- 小程序---textarea踩坑
- bzoj 2427
- VMPlayer Ubuntu 16.04 Copy and Paste with Host 主机与宿机之间的复制粘贴
- Oracle 11g 静默安装脚本
- SqlMapConfig.xml全局配置文件介绍——(四)
- Appium+python HTML测试报告(1)(转)