#P18702. Treelection
Treelection
Treelection
公司 X 有 名员工,编号为 到 。对于每个 ,编号为 ()的员工是员工 的直属经理。员工 是 CEO,没有经理。
如果员工 是员工 的直属经理,或者存在员工 ,使得 是 的直属经理且 是 的领导,则称 是 的领导。也就是说,领导是管理树中的严格祖先,不包括员工自己。
公司 X 想通过选举成立员工委员会。每位员工都会投票,CEO 除外。不幸的是,选举受到操纵:每位投票员工只能投给自己的一位领导。
请找出哪些员工有可能成为选举的唯一胜者。一名员工是唯一胜者,当且仅当他获得的票数严格多于其他任意员工。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例包含两行:第一行包含整数 ;第二行包含 个整数 。保证对所有合法下标 ,均有 。
数据范围
- 。
- 。
- 所有测试用例中, 的总和不超过 。
- 对所有 ,有 。
输出格式
对每个测试用例输出一行,一个长度为 的字符串。如果员工 有可能成为唯一胜者,则第 个字符为 1,否则为 0。
样例输入
2
4
1 2 3
5
1 1 2 2
样例输出
1100
10000
样例说明
在第一个测试用例中,如果员工 投给员工 ,员工 和员工 都投给员工 ,则员工 得到 票,员工 得到 票。因此员工 可以成为唯一胜者。