#P12823. 钥匙迷宫

钥匙迷宫

钥匙迷宫

Problem Description

有一个有 2n2n 个节点的树。每个节点拥有一个钥匙或一个锁。钥匙和锁各有 nn 种,编号为 11 到 nn。保证每种钥匙和每种锁均在树上刚好出现一次。 cats 可以选择一个拥有钥匙的节点出发,沿着树的边移动任意多次。cats 每次到达一个拥有钥匙的节点时(包括出发的节点),cats 可以收集这个节点的钥匙。只有当 cats 拥有编号为 ii 的钥匙时,cats 才可以移动到拥有编号为 ii 的锁的节点。钥匙是不会被消耗的,也就是 cats 在获得编号为 ii 的钥匙后,他可以移动到拥有编号为 ii 的锁的节点任意多次。 现在 cats 想知道,对于每个拥有钥匙的节点,如果他选择这个节点作为出发的节点,他能否收集到全部的 nn 种钥匙。你能告诉 cats 答案吗?

Input

第一行包含一个整数 TT (1≤T≤2⋅1041\leq T \leq 2\cdot 10^4),表示一共有 TT 组测试数据。 对于每组测试数据: 第一行为一个整数 nn (1≤n≤2⋅1051\leq n\leq 2\cdot 10^5),表示钥匙的总数和锁的总数。 第二行为 2n2n 个整数 a1,a2,…a2na_1,a_2,\dots a_{2n} (−n≤ai≤n,ai≠0-n \leq a_i \leq n,a_i \neq 0),表示每个节点拥有的钥匙或锁的编号。其中 ai>0a_i > 0 表示这个节点拥有编号为 aia_i 的钥匙,ai<0a_i < 0 表示这个节点拥有编号为 −ai-a_i 的锁。保证每种钥匙和每种锁均在树上刚好出现一次。 接下来 2n−12n - 1 行,每行两个整数 ui,viu_i,v_i (1≤ui,vi≤2n1\leq u_i,v_i\leq 2n),表示一条连接节点 uiu_i 和 viv_i 的边。保证这 2n−12n - 1 条边构成一棵树。 保证所有测试数据的 nn 之和不超过 10610^6。

Output

对于每组测试数据,输出一个长度为 nn 的 0101 字符串。如果 cats 从拥有编号为 ii 的钥匙的节点出发,可以收集到全部的 nn 种钥匙,则字符串中第 ii 个字符为 11。否则字符串中第 ii 个字符为 00。

Sample Input

4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6

Sample Output

1
011
000
000

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(6)