第 6 题 编程题 时间限制： 1000MS 内存限制： 65536KB 题目描述： 编程实现：活动人数 有一个大型企业集团，由N个部门组成，编号从1到N。这些部门之间的层次关系形成了一个树

第 6 题 编程题LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

时间限制： 1000MSLRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

内存限制： 65536KBLRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

题目描述：LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

编程实现：活动人数LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

有一个大型企业集团，由N个部门组成，编号从1到N。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有1个或多个直接下级部门，一个下级部门只有一个直接上级部门。LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. 来的人越多越好；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下集部门可以参加（如下图，如果部门1参加，那么部门2、3不能参加，而部门4、5、6可以参加）。LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

例如：当N=6，每个部门编号为1到6，部门上下级关系和部门的人数如下图所示：LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

注意：示例中，部门1是层级最高的部门，没有直接上级，故将其直接上级部门设为0；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当安排（1、4、5、6）这4个部门参加活动时，人数最多，为11，所以输出11。LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入描述LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行输入一个正整数N（1≤N≤100000），表示集团所有部门的数量LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来有N行，每行输入三个非负整数F、S和C，（0≤F≤N，1≤S≤N，F≠S，1≤C≤1000），F表示是部门S的直接上级，C表示部门S的人数，整数之间用一个空格隔开LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

注意：如果是最上层的部门，其直接上级部门编号为0LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出描述LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出一个整数，表示参加活动的最多人数LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例输入LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

6LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

0 1 2LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1 2 4LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1 3 3LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2 4 3LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3 5 2LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3 6 4LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例输出LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

11LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

评分标准：LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第一组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第二组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第三组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第四组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第五组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第六组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第七组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第八组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第九组数据；LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

10分：能正确输出第十组数据。LRC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库