活动人数 时间限制: 1000MS 内存限制: 65536KB 题目描述： 编程实现：活动人数 有一个大型企业集团，由N个部门组成，编号从1到N。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有1个或多个直接下级部门，一个下级部门只有一个直接上级部门。 本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动： 1. 来的人越多越好； 2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下集部门可以参加（如下图，如果部门1参加，那么部门2、3不能参加，而部门4、5、6可以参加）。 请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。 例如：当N=6，每个部门编号为1到6，部门上下级关系和部门的人数如下图所示： 注意：示例中，部门1是层级最高的部门，没有直接上级，故将其直接上级部门设为0； 当安排（1、4、5、6）这4个部门参加活动时，人数最多，为11，所以输出11。 输入描述 第一行输入一个正整数N（1≤N≤100000），表示集团所有部门的数量 接下来有N行，每行输入三个非负整数F、S和C，（0≤F≤N，1≤S≤N，F≠S，1≤C≤1000），F表示是部门S的直接上级，C表示部门S的人数，整数之间用一个空格隔开 注意：如果是最上层的部门，其直接上级部门编号为0 输出描述 输出一个整数，表示参加活动的最多人数 【样例输入】 6 0 1 2 1 2 4 1 3 3 2 4 3 3 5 2 3 6 4 【样例输出】 11
正确答案：树最大点权独立集DP。dp[u][0]=Σ子max(dp[v][0],dp[v][1])，dp[u][1]=C[u]+Σdp[v][0]，答案max(dp[root])。核心：\ndef dfs(u):\n t=val[u];nt=0\n for v in ch[u]:a,b=dfs(v);t+=b;nt+=max(a,b)\n return t,nt\nprint(max(dfs(root)))
答案解析
评分标准：
10分：能正确输出第一组数据；
10分：能正确输出第二组数据；
10分：能正确输出第三组数据；
10分：能正确输出第四组数据；
10分：能正确输出第五组数据；
10分：能正确输出第六组数据；
10分：能正确输出第七组数据；
10分：能正确输出第八组数据；
10分：能正确输出第九组数据；
10分：能正确输出第十组数据。
【解析】本题改编自洛谷 P1352，涉及到提高级的树形 DP 知识，要弄懂本题，至少需要知道 DP 和邻接表的前置知识。
n 个部门除了最上层部门，其他部门都有一个直接上级部门，这一关系满足树的数据结构性质，可以使用邻接表存储。每个部门相当于树上的一个结点，部门人数则是结点上的权值。问题转变成——在不选择树中相邻结点的前提下，求从树中选出结点的权值之和的最大值。
考虑树中以结点 u 为根的子树，u 本身有选取与不选取两种决策，并会影响到它的父亲与儿子结点，因此，可以以 f[u][0]、f[u][1] 分别表示不选取、选取结点 u 两种情形下，以结点 u 为根的子树能够选出的权值之和的最大值，则状态转移方程为：
f[u][0] = max {f[v1][0], f[v1][1]} + max {f[v2][0], f[v2][1]} + · · · + max {f[vm][0], f[vm][1]}
f[u][1] = au + f[v1][0] + f[v2][0] + · · · + f[vm][0]
其中 v1, v2, . . . , vm 都为 u 的儿子结点，au 为结点 u 的权值。
实现细节上，注意本题不保证树的根结点是 1，因此需要在建树时找到根结点 root，DFS 时从 root 出发，最终答案即为max {f[root][0], f[root][1]}
试卷来源：202305(第14届)蓝桥杯C++编程青少组(省赛)真题