[蓝桥杯青少年组省赛 2023] 活动人数

Luogu
IDLGB4275
Time1000ms
Memory512MB
DifficultyP3
2023树形 DP蓝桥杯青少年组
有一个大型企业集团,由 $N$ 个部门组成,编号从 $1$ 到 $N$。这些部门之间的层次关系形成了一个树状结构,一个上级部门可能会有 $1$ 个或多个直接下级部门,一个下级部门只有一个直接上级部门。 本月集团举办了一个大型活动,这次的活动组织方按如下要求安排活动: 1. 来的人越多越好; 2. 如果一个上级部门参加本次活动,那么他们的直接下级部门就不能参加,而他的间接下级部门可以参加(如下图,如果部门 $1$ 参加,那么部门 $2,3$ 不能参加,而部门 $4,5,6$ 可以参加)。 请你帮他们计算一下,如何安排可以使参加活动的人数最多,并输出参加活动的最多人数。 例如:当 $N=6$,每个部门编号为 $1$ 到 $6$,部门上下级关系和部门的人数如下图所示: ![](https://cdn.luogu.com.cn/upload/image_hosting/ej7lvi7g.png) 注意:示例中,部门 $1$ 是层级最高的部门,没有直接上级,故将其直接上级部门设为 $0$; 当安排($1,4,5,6$)这 $4$ 个部门参加活动时,人数最多,为 $11$,所以输出 $11$。 ## Input 第一行输入一个正整数 $N$($1 \leq N \leq 100000$),表示集团所有部门的数量。 接下来有 $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$ 的人数,整数之间用一个空格隔开。 注意:如果是最上层的部门,其直接上级部门编号为 $0$。 ## Output 输出一个整数,表示参加活动的最多人数。 [samples] ## Note **【评分标准】** - $10$ 分:能正确输出第一组数据; - $10$ 分:能正确输出第二组数据; - $10$ 分:能正确输出第三组数据; - $10$ 分:能正确输出第四组数据; - $10$ 分:能正确输出第五组数据; - $10$ 分:能正确输出第六组数据; - $10$ 分:能正确输出第七组数据; - $10$ 分:能正确输出第八组数据; - $10$ 分:能正确输出第九组数据; - $10$ 分:能正确输出第十组数据。
Samples
Input #1
6
0 1 2
1 2 4
1 3 3
2 4 3
3 5 2
3 6 4
Output #1
11
API Response (JSON)
{
  "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. 如果一个上级部门参加本次活动,那么他们的直接下级部门就不能参加,而他的间接下级部门可以...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments