Cowntact Tracing

题目描述

农夫约翰有 $N$ 头奶牛（$2\le N\le 10^5$），编号为 $1\dots N$，奶牛之间的连接关系由一棵树描述。不幸的是，有一种疾病正在传播。 起初，有一些奶牛一开始就被感染。每过一晚，一头被感染的奶牛会把疾病传播给它的相邻奶牛。一旦一头奶牛被感染，她将一直保持感染状态。 经过若干个夜晚后，农夫约翰意识到出现了问题，于是他检测奶牛以确定哪些奶牛患病。 给定 $Q$（$1\le Q\le 20$）个不同的“夜晚数”取值，每个都是 $[0,N]$ 范围内的整数。对于每个夜晚数，确定最少可能有多少头奶牛一开始就患病；或者判断该夜晚数与给定信息不一致。

输入格式

第一行包含 $N$。 第二行包含一个长度为 $N$ 的二进制字符串，其中第 $i$ 位为 1 表示第 $i$ 头奶牛被感染，为 0 则表示未感染。至少有一头奶牛被感染。 接下来 $N-1$ 行包含树的边。 然后输入 $Q$，接着输入这 $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

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

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

3
1
1
-1
-1
-1

提示

对于前四个查询，一种可能是只有奶牛 3 一开始患病。对于第五个查询（1 个夜晚），一种可能是奶牛 2 和 4 一开始患病。对于第六个查询（0 个夜晚），一种可能是所有 5 头奶牛一开始患病。 对于第一个查询（0 个夜晚），一种可能是所有 10 头奶牛一开始患病。对于第二个查询（1 个夜晚），一种可能是奶牛 2、7 和 9 一开始患病。对于第三个查询（2 个夜晚），一种可能是奶牛 2 和 9 一开始患病。对于第四到第十一个查询，一种可能是只有奶牛 7 一开始患病。 对于第一个查询（0 个夜晚），一种可能是奶牛 1、2 和 3 一开始患病。对于第二个查询（1 个夜晚），一种可能是只有奶牛 2 一开始患病。对于第三个查询（2 个夜晚），一种可能是只有奶牛 1 一开始患病。对于第四到第六个查询，不存在一致的可能性。 评分： Inputs 4-5: $N \le 10$ Inputs 6-8: 所有奶牛都被感染。 Inputs 9-11: $N \le 400$ Inputs 12-23: 无额外限制。 题目鸣谢：Suhas Nagar and Brandon Wang

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum