第 6 题 【 问答题 】
活动人数
时间限制: 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），表示集团所有部门的数量
接
【蓝桥杯C++编程竞赛】是一场针对青少年的编程竞赛，主要考察参赛者的C++编程能力和算法设计能力。在此次竞赛中，题目的重点在于解决实际问题，比如活动人数的最大化安排，以及一系列的算法题目。
【第6题 - 问答题】此题涉及到树形结构和递归算法的应用。题目设定一个大型企业集团的部门构成一个树状结构，其中每个部门有0或多个直接下属。活动规则规定，如果一个上级部门参加，其直接下属部门不能参加，但间接下属可以。目标是找出一种安排方式，使得参加活动的总人数最多。解决这个问题的关键在于遍历树的深度优先搜索(DFS)或广度优先搜索(BFS)，同时使用动态规划来记录每个节点的最大参与人数。在遍历过程中，要避免重复计数，确保上级部门的参与不会影响到其间接下属。最后输出参加活动的最多人数。
【C++知识点】
1. **数据类型**：题目中提到了`bool`类型，`bool`在C++中占用1个字节。
2. **结构体**：C++的结构体可以包含成员变量、静态成员变量，但不能包含成员函数或构造函数，因为它们是类的特性。
3. **二叉树**：题目中提到了二叉树的高度，一个含62个节点的完全二叉树高度为5，因为一棵高度为h的完全二叉树至少有2^(h-1)+1个节点。
4. **数组**：数组是连续存储的数据结构，所有元素类型相同，索引从0开始，数组名代表首地址。
5. **特殊运算符**：这个题目引入了一个自定义运算符">>>"，需要理解其功能并编写对应的实现。
【算法题目】
1. 特殊运算符：需要理解运算符">>>"的逻辑，根据给定的规则计算结果。
2. 四叶玫瑰数：这是一个寻找特定性质数字的问题，需要进行位操作和数学计算。
3. 质因数的个数：要求统计质因数，需要用到质数判断和质因数分解，可能涉及质数表或者筛法。
4. 最大的矩形纸片：此题是找最大矩形问题，可以利用栈来求解，类似于计算最大连续子数组和的问题。
蓝桥杯C++编程竞赛注重对参赛者的基础语法掌握、算法理解与实现、以及逻辑思维能力的综合考察。参赛者不仅需要熟悉C++的基本语法，还要熟练运用数据结构和算法，如树的遍历、动态规划、位操作等，以解决实际问题。
