提前上学之后,要做的东西就多了起来,To Do List 直接变成了 To Do Tree。

Mike 现在有 

n

 个ddl,每星期 Mike 最多能肝 

m

 个ddl,否则 Mike 会爆肝猝死。而且ddl之间有一些依赖关系,开始第 

i

 个ddl前必须先做完第 

fi

 个ddl(

fi<i

),比如说,叉掉假算法之前必须先写一个靠谱的std。ddl间的依赖关系构成了一颗以 

1

 号ddl为根的树。

现在Mike想知道他最少需要几星期才能肝完所有的ddl。

注意:每星期所有ddl会在周日晚23:59:59同时被肝完,也就是说,一个星期内不能同时肝第 

fi

 个ddl和第 

i

 个ddl。

输入格式

第一行两个整数 

n,m

接下来一行 

n1

 个整数,分别表示 

f2,f3,,fn

输出格式

第一行输出一个整数 

t

,表示最少需要的时间。

接下来 

t

 行,第 

i

 行表示第 

i

 星期 Mike 肝的ddl,其中第一个整数 

si

 表示 Mike 这周肝的ddl个数,接下来 

si

 个整数分别是 Mike 这周肝的ddl标号。相邻两个整数间用空格隔开。行末需要一个空格符。

注意最后一行需要回车符,格式不对将会被判为

0

分。

样例一

input

output

explanation

如果时刻 

2

 没有肝掉第 

2

 个ddl,则无法在最短时间内肝完所有ddl。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

对于所有数据,

n105,mn,fi<i

子任务 分值 限制
1

30

n10

2

30

n16

3

6

m=1

4

34

n105

时间限制

1s

空间限制

看出是一个贪心 大胆猜测结论

按照每个点子树内最深的深度贪心即可 证明看uoj blog有官方题解

http://wuhongxun.blog.uoj.ac/blog/3670

 

分类: 贪心

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论