Problem1619--PIPI处理任务

1619: PIPI处理任务

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

由于过年摆烂,PIPI现在有一堆任务紧急需要处理,为了尽快完成,PIPI使用了分身术,现在有两个PIPI在同时处理任务
已知任务之间是存在依赖关系的,即对于某个任务,需要先完成他的前导任务(如果非空),才能开始执行该任务。任务的依赖关系是一棵二叉树,其中 root 为根任务,root.left 和 root.right 为他的两个前导任务(可能为空),root.val 为其自身的执行时间。
PIPI的任意一个分身在处理某个任务时,可以在任何时刻暂停当前任务的执行,并保留当前执行进度。在下次继续执行该任务时,会从之前停留的进度开始继续执行。暂停的时间可以不是整数。
由于分身的存在,PIPI可以同时执行两个任务,但是同一个任务不能同时由两个分身一起处理,给定这堆任务,请求出PIPI处理完所有任务的最小时间



Input

输入有一行,表示一堆任务,这些任务组成了一颗任务树,我们将这棵树以先序遍历的方式输出,为空的结点输出-1,结点之间用空格隔开
其中,结点个数的范围为[0, 1000],结点任务处理时间范围为[1, 10000]

Output

对于这一堆任务,给出PIPI处理完这些任务所需的最小时间,结果保留一位小数

Sample Input

1 3 -1 -1 2 4 -1 -1 4 -1 -1

Sample Output

7.5

Source/Category

困难