{"problem":{"name":"[USACO23DEC] Cowntact Tracing P","description":{"content":"Farmer John 有依次编号为 $1\\dots N$ 的 $N$（$2\\le N \\le 10^5$）头奶牛，奶牛间的关系可以用树结构描述。不幸的是，有一种疾病正在传播。 最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它的邻居。一旦奶牛被感染，她就会持续处于感染状态。经过一些晚上，Farmer John 意识到这样的情况，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。 你","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9983"},"statements":[{"statement_type":"Markdown","content":"Farmer John 有依次编号为 $1\\dots N$ 的 $N$（$2\\le N \\le 10^5$）头奶牛，奶牛间的关系可以用树结构描述。不幸的是，有一种疾病正在传播。\n\n最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它的邻居。一旦奶牛被感染，她就会持续处于感染状态。经过一些晚上，Farmer John 意识到这样的情况，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。\n\n你将得到 $Q$（$1\\le Q \\le 20$）个不同的夜晚数，每个都是 $[0,N]$ 范围内的整数。对于每个夜晚数，请找出最少有多少头奶牛最初可能感染了这种疾病，或者报告夜晚数与给出的信息不符。\n\n## Input\n\n第一行为一个整数 $N$。\n\n接下来一行，包含长度为 $N$ 的由 $1$ 和 $0$ 组成的位串。其中 $1$ 表示一头被感染的奶牛，$0$ 表示一头在经过若干晚之后仍未被感染的奶牛。\n\n接下来 $N-1$ 行描述了树的边。\n\n接着输入 $Q$ 和 $Q$ 个夜晚数。\n\n## Output\n\n输出 $Q$ 行，表示每个夜晚数的答案。若无解，输出 $-1$。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n对于前四个询问，一种可能是只有 $3$ 号奶牛一开始被感染。对于第五组询问（$1$ 晚），一种可能是 $2,4$ 号奶牛一开始被感染。对于第六组询问（$0$ 晚），一种可能是所有的五只奶牛在一开始都被感染。\n\n### 样例解释 2\n\n对于第一组询问（$0$ 晚），一种可能是所有的十只奶牛一开始都被感染。对于第二组询问（$1$ 晚），一种可能是 $2,7,9$ 号奶牛一开始被感染。对于第三组询问（$2$ 晚），一种可能是 $2,9$ 号奶牛一开始被感染。对于第四至第十一组询问，一种可能是只有 $7$ 号奶牛一开始被感染。\n\n### 样例解释 3\n\n对于第一组询问（$0$ 晚），一种可能是 $1,2,3$ 号奶牛一开始被感染。对于第二组询问（$1$ 晚），一种可能是只有 $2$ 号奶牛一开始被感染。对于第三组询问（$2$ 晚），一种可能是只有 $1$ 号奶牛一开始被感染。对于第四至第六组询问，不可能满足题给条件。\n\n### 测试点性质\n\n- 测试点 $4-5$ 满足 $N \\le 10$。\n- 测试点 $6-8$ 满足所有奶牛都被感染。\n- 测试点 $9-11$ 满足 $N \\le 400$。\n- 测试点 $12-23$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9983","tags":["动态规划 DP","贪心","USACO","点分治","2023","O2优化","树形 DP"],"sample_group":[["5\n11111\n1 2\n2 3\n3 4\n4 5\n6\n5\n4\n3\n2\n1\n0","1\n1\n1\n1\n2\n5"],["10\n1111111111\n1 2\n2 3\n2 4\n2 5\n2 6\n6 7\n7 8\n8 9\n9 10\n11\n0\n1\n2\n3\n4\n5\n6\n7\n8\n9\n10","10\n3\n2\n1\n1\n1\n1\n1\n1\n1\n1"],["5\n11100\n1 2\n2 3\n3 4\n4 5\n6\n0\n1\n2\n3\n4\n5","3\n1\n1\n-1\n-1\n-1"]],"created_at":"2026-03-03 11:09:25"}}