{"problem":{"name":"[蓝桥杯青少年组省赛 2023] 活动人数","description":{"content":"有一个大型企业集团，由 $N$ 个部门组成，编号从 $1$ 到 $N$。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有 $1$ 个或多个直接下级部门，一个下级部门只有一个直接上级部门。   本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：   1. 来的人越多越好；   2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下级部门可以","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4275"},"statements":[{"statement_type":"Markdown","content":"有一个大型企业集团，由 $N$ 个部门组成，编号从 $1$ 到 $N$。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有 $1$ 个或多个直接下级部门，一个下级部门只有一个直接上级部门。  \n\n本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：  \n\n1. 来的人越多越好；  \n2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下级部门可以参加（如下图，如果部门 $1$ 参加，那么部门 $2,3$ 不能参加，而部门 $4,5,6$ 可以参加）。  \n\n请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。  \n\n例如：当 $N=6$，每个部门编号为 $1$ 到 $6$，部门上下级关系和部门的人数如下图所示：  \n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ej7lvi7g.png)\n\n注意：示例中，部门 $1$ 是层级最高的部门，没有直接上级，故将其直接上级部门设为 $0$；  \n\n当安排（$1,4,5,6$）这 $4$ 个部门参加活动时，人数最多，为 $11$，所以输出 $11$。  \n\n## Input\n\n第一行输入一个正整数 $N$（$1 \\leq N \\leq 100000$），表示集团所有部门的数量。\n\n接下来有 $N$ 行，每行输入三个非负整数 $F$、$S$ 和 $C$，（$0 \\leq F \\leq N$，$1 \\leq S \\leq N$，$F \\neq S$，$1 \\leq C \\leq 1000$），$F$ 表示是部门 $S$ 的直接上级，$C$ 表示部门 $S$ 的人数，整数之间用一个空格隔开。  \n\n注意：如果是最上层的部门，其直接上级部门编号为 $0$。\n\n## Output\n\n输出一个整数，表示参加活动的最多人数。\n\n[samples]\n\n## Note\n\n**【评分标准】**\n\n- $10$ 分：能正确输出第一组数据；  \n- $10$ 分：能正确输出第二组数据；  \n- $10$ 分：能正确输出第三组数据；  \n- $10$ 分：能正确输出第四组数据；  \n- $10$ 分：能正确输出第五组数据；  \n- $10$ 分：能正确输出第六组数据；  \n- $10$ 分：能正确输出第七组数据；  \n- $10$ 分：能正确输出第八组数据；  \n- $10$ 分：能正确输出第九组数据；  \n- $10$ 分：能正确输出第十组数据。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4275","tags":["2023","树形 DP","蓝桥杯青少年组"],"sample_group":[["6\n0 1 2\n1 2 4\n1 3 3\n2 4 3\n3 5 2\n3 6 4","11"]],"created_at":"2026-03-03 11:09:25"}}