给定一棵树,以及树各节点的点权(点权为偶数)。起初有一个棋子在树的根结点(结点 1)处。
- A 与 B 两人轮流操作:将棋子移动到其所在节点的某个叶子节点。
- 到某个节点的得分定义为:棋子经过所有结点点权的中位数。K 个数的中位数定义如下:
- 当 K 为奇数时,中位数为 K 个数中第 2K+1 小的值。
- 当 K 为偶数时,中位数为 K 个数中第 2K 小与第 2K+1 小的两数的平均值。
- A 希望最后得分尽可能大,B 希望最后得分尽可能小。
- 当棋子到达某个叶节点时,游戏结束。
若 A 先手操作,A,B 都采取最优策略,求最终得分。