首页 > 试题广场 >

服务器数据分发

[编程题]服务器数据分发
  • 热度指数:634 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
【题干描述】:
我们共有n台服务器,每台服务器可以和若干个子服务器传输数据,n台服务器组成一个树状结构。
现在要将一份数据从root节点开始分发给所有服务器。
一次数据传输需要一个小时时间,
一个节点可以同时对k个儿子节点进行并行传输,
不同节点可以并行分发。
问,全部分发完成,最短需要多少小时?

【示例】:
当共有5台服务器,其树状结构为
       0
     /     \
   1      2
  /   \
 3    4
假设每一台服务器同时可以对1个儿子节点(k=1)并行传输,最优的数据传输过程示例如下:
    第一个小时,0 -> 1;
    第二个小时,1->3 & 0->2;
    第三个小时,1 -> 4;
所以当k=1时,全部分发完成最短需要3个小时。
假设每一台服务器同时可以对2个儿子节点(k=2)并行传输,最优的数据传输过程示例如下:
    第一个小时,0 -> 1 & 0 -> 2;
    第二个小时,1 -> 3 & 1 -> 4;
所以当k=2时,全部分发完成最短需要2个小时。

输入描述:
首行输入包含两个参数,分别表示每台服务器允许k个子节点并行传输,以及剩余输入行数。
其他行用于服务器树状结构描述,每一行表示一个父节点以及父节点对应的所有子节点。每一行都通过空格符分割不同数字,第一位数字为父节点及其所有子节点个数,第二位数字为父节点编号,其他数字为对应的子节点编号。


输出描述:
输出全部服务器分发完成,需要的最短时间。
示例1

输入

1 2
3 0 1 2
2 1 3

输出

2

备注:
1、服务器树状结构只有一个根节点,且根节点编号为0。

2、服务器个数n未知,但服务器编号取值范围为[0, n-1]。

3、n<=1000000