题解

题面描述

有一个探险家初始时魔力值为 $0$。给定一棵以节点 $1$ 为根的树，共有 $n$ 个节点，每个节点上刻有一个符文 $\texttt{U}$ 或 $\texttt{D}$。当探险家到达某个节点时，会根据节点上的符文进行操作：若是 $\texttt{U}$ 则魔力值增加 $1$，若是 $\texttt{D}$ 则魔力值减少 $1$。
现在，对于任意的节点 $i$（$1\le i\le n$），如果探险家从节点 $i$ 出发（出发时先触发该节点的符文），之后沿着树中从当前节点的“子结点”向下移动（每次沿唯一的路径向下移动），判断是否存在一条路径使得探险家在移动过程中某个前缀处达成平衡，即魔力值重新变为 $0$（注意，一旦在移动过程中魔力值变为 $0$，就算成功，不必继续移动）。