题解

题面描述

有一个机器人初始时在坐标 $0$ 上，机器人可以每次向上或向下移动 $1$ 个单位。同时给定一棵以节点 $1$ 为根的树，共有 $n$ 个节点，每个节点上标有一个字符 $U$ 或 $D$。当小红走到某个节点时，会根据节点上的字母进行操作：若是 $U$ 则机器人向上移动 $1$，若是 $D$ 则向下移动 $1$。
现在，对于任意的节点 $i$（$1\le i\le n$），如果小红从节点 $i$ 出发（出发时先将该节点对应的移动操作执行），之后沿着树中从当前节点的“子结点”向下移动（每次沿唯一的路径向下移动），判断是否存在一种移动方案使得机器人在移动过程中最终会回到坐标 $0$（注意，一旦在移动过程中机器人到达 $0$，就算成功，不必继续移动）。

思路

题目内容

小红正在垂直面板上操控一个机器人，初始时机器人位于坐标 $0$ ，机器人可以执行两种操作。

1.向上移动一个单位。

2.向下移动一个单位。

小红同时拿到一棵树，根节点为 $1$ ，每个结点上有一个字母" $U$" 或 "$D$" ，如果小红走到 "$U$" 则将机器人向上移动一个单位，如果小红走到 "$D$" 则将机器人向下移动一个单位。

现在她想让你判断对于任意的 $i(1≤i≤n)$ ，小红若从结点 $i$ 开始出发，每次随机的向当前结点的子结点随机移动，是否存在一种移动方式使得机器人最终会再到达坐标 $0$ ，值得注意的是，当小红离开结点 $i$ 后，若中途移动过程中机器人若到达坐标 $0$ ，则认为机器人已经到达坐标 $0$ ，不需要再移动。

输入描述

第一行个整数 $n(1 ≤ n ≤2×10^5)$ ，表示树的结点数。

第二行一个长度为 $n$ 的字符串，第 $i$ 个字符表示结点 $i$ 上的字母，保证输入仅含 "$U$" 和 "$D$" 。

接下来 $n-1$ 行，每行两个整数 $u,v(1 ≤ u,v≤n,u≠v)$ ，表示结点 $u$ 和 $v$ 之间有一条边。

输出描述

输出 $n$ 个整数，第 $i$ 个整数表示小红从结点 $i$ 开始出发，是否存在一种移动方式使得机器人最终会再到达 $0$ 号结点，如果可以输出 $1$ ，否则输出 $0$ 。

样例1

输入

5
DDUUD
1 2
1 3
2 4
3 5

输出

1 1 1 0 0