网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
立春树
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | tdec.in | 输出文件 | tdec.out |
Farmer John正在装饰他的立春树(就像圣诞树,但是流行得晚3个月) 它由一个N(1 <= N <= 100,000)个点的树来表示, 标号为1到N,1号点为根。 其他节点i都有个父亲P_i(1 <= P_i <= N)。1号点没有父亲,(输入中用-1表示), 因为它是树根。 每个节点i都有一个对应的以它为根的子树(包括大小为1的子树)。FJ想确保点i对应的子树 有至少C_i个(1 <= C_i <= 10,000,000)个装饰物分散在整个子树上。 他还想用最少的时间 来放置所有装饰物(需要K*T_i的时间在点i放置K个装饰物(1 <= T_i<= 100)). 帮助FJ计算出最少需要的时间放置装饰物来满足要求。答案可能超过32位整数,但是保证 会在64位有符号整数范围内。 例如,考虑下面这棵树: 1 | 2 | 5 / 4 3 假设FJ需要满足下列要求 该子树至少需要的装饰物数 | 放置一个的时间 | | 子树的根 | C_i | T_i --------+--------+------- 1 | 9 | 3 2 | 2 | 2 3 | 3 | 2 4 | 1 | 4 5 | 3 | 3 那么FJ可以放置像下面这样所有的装饰物,用了20的时间: 1 [0/9(0)] 图例: 元素# [该点放置的装饰物/ | 子树中总共的装饰物数(该点总时间)] 2 [3/9(6)] | 5 [0/6(0)] / [1/1(4)] 4 3 [5/5(10)] 问题名称: tdec 输入格式: * 第一行: 一个整数: N * 第二行到第N+1行: 第i+1行有三个整数,P_i,C_i,T_i。 样例输入 (tdec.in): 5 -1 9 3 1 2 2 5 3 2 5 1 4 2 3 3 输出格式: * 第一行: 一个整数:放置装饰物的最少时间 样例输出 (tdec.out): 20