小M种树

题号：NC284892
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小 M 出身于贵族学校，擅长园艺。除了会给黄瓜浇水，她还会给一棵树上色。

$\hspace{15pt}$ 这棵树的形态与图论中描述的有根树相同，是以 $1$ 为根节点的 $n$ 个节点、 $n-1$ 条边的简单连通图。
$\hspace{15pt}$ 一开始，树上每个节点染上了红色或蓝色。定义以节点 $i$ 为根的子树的差异 $D(i)$ 为该子树中红色点数与蓝色点数的差的绝对值；而一棵树的不平均程度，等于 $\sum\limits_{i=1}^n D(i)$ 。
$\hspace{15pt}$ 现在小 M 有机会，可以修改其中一个节点的颜色（原来是红色就染成蓝色，反之同理）。小 M 想问你，有哪些修改的方案，可以让这棵树的不平均程度相比修改前更小。

$\hspace{15pt}$ 本题有多组数据，你需要对每组数据都求出对应的答案。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表树上的点数。 
第二行输入一个长度为  、仅由  和  组成的字符串  ，代表树上的节点颜色。其中，如果 ，那么代表节点  是红色的；反之，如果 ，代表节点  是蓝色的。
此后  行，第  行输入两个正整数  ，代表树上第  条边连接节点  和  。保证这  条边一定可以形成一棵大小为  的树。

除此之外，保证单个文件的  之和不超过  。

输出描述:

对于每一组测试数据，在单独的一行上输出一个长度为  的  字符串，代表每一个节点修改后，树的不平均程度是否变小。其中，如果  ，那么代表修改第  个节点后可以让不平均程度变小；反之，输出 。

示例1

输入

复制

3
4
BRBB
3 2
4 2
1 3
7
RRRRBRR
2 3
7 3
4 2
5 2
1 5
6 3
7
BRBBBRB
2 7
4 7
1 2
3 2
6 2
5 4

输出

复制

1010
1111011
1011101

说明

对于第一组测试数据，树的形态如下图所示。
初始时，树的不平均度为  。
如果修改了第一个节点的颜色，那么  ，其余不变，新的不平均度为  ，变小了；
如果修改了第二个节点的颜色，不平均度变为  ；
如果修改了第三个节点的颜色，不平均度变为  ；
如果修改了第四个节点的颜色，不平均度变为  ；
因此，修改第一、三个点，不平均度会比原来小，输出  。