#abc218g. [abc218_g]Game on Tree 2

[abc218_g]Game on Tree 2

给定一棵树,以及树各节点的点权(点权为偶数)。起初有一个棋子在树的根结点(结点 11)处。

  • AABB 两人轮流操作:将棋子移动到其所在节点的某个叶子节点。
  • 到某个节点的得分定义为:棋子经过所有结点点权的中位数。KK 个数的中位数定义如下:
    • KK 为奇数时,中位数为 KK 个数中第 K+12\frac{K+1}{2} 小的值。
    • KK 为偶数时,中位数为 KK 个数中第 K2\frac{K}{2} 小与第 K2+1\frac{K}{2}+1 小的两数的平均值。
  • AA 希望最后得分尽可能大,BB 希望最后得分尽可能小。
  • 当棋子到达某个叶节点时,游戏结束。

AA 先手操作,AABB 都采取最优策略,求最终得分。