题目描述

题目译自 USACO 2023 December Contest, Platinum Problem 1. Cowntact Tracing

FJ 有 $N$ 头奶牛，编号为 $1$ 到 $N$，这些奶牛之间的关系可以用一棵树表示。不幸的是，有一场传染病正在传播。

最初，某些奶牛受到感染。每晚，一头被感染的奶牛会传染它的邻居。每当一头奶牛被感染，她就会保持被感染的状态。过了几个晚上，FJ 意识到出了问题，于是他对奶牛进行了检测，以确定哪些奶牛被感染了。

给定 $Q$ 个互不相同的值，这些值代表过去的晚上数，每个整数都在 $[0,N]$ 中。对于每个过去的晚上数，确定最初被感染的奶牛可能的最少头数，或者判定该数与给定信息不一致。

译者注：给定 $Q$ 个互不相同的整数，把每个整数当做 FJ 在这天晚上去观察奶牛的感染情况，问最初至少有多少奶牛被感染了，或者判定这天晚上的感染情况不可能是给定的感染情况。

输入格式

第一行一个整数 $N\ (2\le N\le 10^5)$。

第二行包含一个长度为 $N$ 的 01 串，其中第 $i$ 个字符为 1 表示第 $i$ 头奶牛被感染了，0 表示没有被感染。保证至少一头奶牛被感染了。

接下来 $N-1$ 行描述这棵树。

接下来一行一个整数 $Q\ (1\le Q\le 20)$ 表示询问个数。

接下来 $Q$ 行每行一个整数，表示过去的夜晚数。

输出格式

输出 $Q$ 行，每行输出对于每个询问的答案。如果不一致输出 $-1$。

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

1
1
1
1
2
5

对于前四个询问，一种可能是只有奶牛 $3$ 最初被感染了。对于第五个询问（过了一个晚上），一种可能是最初奶牛 $2$ 和奶牛 $4$ 被感染了。对于第六个询问（过了 $0$ 个晚上），一种可能是所有五头奶牛都被感染了。

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

10
3
2
1
1
1
1
1
1
1
1

对于第一个询问（过了 $0$ 个晚上），一种可能是所有十头奶牛都被感染了。对于第二个询问（过了一个晚上），一种可能是奶牛 $2,7,9$ 最初被感染了。对于第三个询问（过了两个晚上），一种可能是奶牛 $2,9$ 最初被感染了。对于第四到第十一个询问，一种可能是最初只有奶牛 $7$ 被感染了。

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

3
1
1
-1
-1
-1

对于第一个询问（过了 $0$ 个晚上），一种可能是奶牛 $1,2,3$ 被感染了。对于第二个询问（过了一个晚上），一种可能是只有奶牛 $2$ 最初被感染了。对于第三个询问（过了两个晚上），一种可能是只有奶牛 $1$ 最初被感染了。对于第四到第六个询问，没有符合条件的可能性。

数据范围与提示

• 测试点 $4\sim 5$：$N\le 10$
• 测试点 $6\sim 8$：所有奶牛都被感染了
• 测试点 $9\sim 11$：$N\le 400$
• 测试点 $12\sim 23$：无附加限制

Problem credits: Suhas Nagar and Brandon Wang