题解

思路

棋子进入一棵子树后，会先取完其中所有硬币再离开，且不会再次进入。

做法

令 $siz_v$ 为子树大小，$get_v$ 为在顶点 $v$ 处由当前玩家先取根硬币时，先手最终得到的硬币数。偶数大小的儿子处理完后轮到同一方继续选择，其中先手所得不超过一半的应优先处理，超过一半的留到最后；奇数大小的儿子会交换下一次选择者，因此按 $2get_u-siz_u$ 从小到大排列并交替归入双方。按这个次序累加各儿子的贡献，再加上顶点 $v$ 的一枚硬币，就得到 $get_v$。

复杂度

由于父节点编号小于子节点，可以按编号逆序完成树形动态规划；所有奇数子树贡献的排序总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$，答案为 $get_1$。