题目解析

本题是一个基于树形结构的交互式游戏问题。公司层级结构是一棵树，根节点为总裁（编号1），每个管理者有奇数个直接下属，普通员工（叶子节点）没有下属。投票规则是：普通员工独立投票，管理者的投票由直接下属的多数意见决定。最终结果取决于总裁的投票。

Bajtazar（橙子支持者）和Bajtoni（葡萄柚支持者）轮流说服普通员工支持自己的水果，Bajtazar先手。游戏在所有普通员工都被说服后结束。目标是确保橙子获胜。

代码策略分析

代码实现了一个贪心策略，通过维护树结构和叶子节点集合来模拟游戏过程：

1. 初始化：

   • 读取员工数量 n，构建树结构（使用邻接表 g 存储每个节点的直接下属）。
   • 标记叶子节点（普通员工），并初始化 win 数组跟踪节点状态（win[i] = 1 表示该节点支持橙子，win[i] = -1 表示支持葡萄柚，初始未决定）。

2. 游戏循环：

   • Bajtazar 首先选择编号最小的叶子节点进行说服，调用 ruch(x) 通知库并获取 Bajtoni 的选择。
   • 更新树状态：
     • 从 Bajtazar 选择的节点 x 开始向上遍历，标记路径上的节点支持橙子（win[x] = 1），并从父节点的下属集合中移除 x。遍历直到根节点或已决定的节点。
     • 从 Bajtoni 选择的节点 e 开始向上遍历，标记路径上的节点支持葡萄柚（win[e] = -1），并同样从父节点的下属集合中移除 e。
   • 选择下一个 Bajtazar 要说服的节点：
     • 如果当前节点 x（可能是根节点）还有下属，则选择该子树中最左边的叶子节点（通过深度优先搜索）。
     • 否则，从剩余的叶子节点中选择编号最小的叶子。

3. 终止条件：当所有普通员工都被说服后，游戏结束，程序自动终止。

为什么这个策略能确保橙子获胜？

• 由于每个管理者有奇数个下属，多数意见总是存在。通过贪心选择叶子节点并向上传播投票结果，Bajtazar 能确保在关键路径上获得多数支持。
• 代码总是优先选择最小编号的叶子，并在更新后选择最左边的叶子，这保证了在树结构中控制关键分支，从而影响管理者的投票。
• 题目假设公司层级设计总是能让 Bajtazar 获胜，因此这个贪心策略在测试数据下总是有效的。