A90541.「USACO 2023.12 Platinum」Cowntact Tracing

题目译自 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$。

• 测试点 $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