题解

思路

Alice 能获胜，当且仅当初始状态已经存在一个确定的子树，其 mex 为 $K$，或者她能通过一次操作造出这样的子树；若她无法一步做到，Bob 总能在受影响的最深未确定子树中写入 $K$，继续维持这一状态。

做法

于是枚举子树根 $v$：子树内不能已经出现 $K$，未写数的顶点至多一个，并且 $0,1,\ldots,K-1$ 中已经出现的不同数的个数加上空位数至少为 $K$。满足这些条件的子树恰能在零步或一步内被补成 mex 为 $K$。

对每个 $v$ 遍历一次它的整棵子树，用时间戳数组统计小于 $K$ 的不同数，同时统计空位并检查 $K$，即可完成判定。

复杂度

每组数据的时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$。