#P18091. Zebra Crossing
Zebra Crossing
Zebra Crossing
题目描述
给定一棵有 个结点的树,编号为 。长度为 的二进制串 描述结点颜色: 表示黑色, 表示白色。
你有跳跃能力 。在结点 时,可以跳到任意满足 的结点 ,其中距离是两点间简单路径的边数。跳跃途中经过的结点不算落点。
对每个目标结点 ,独立地从结点 出发,经过若干次跳跃到达 ,求跳跃后落在黑色结点上的次数最少是多少。
起点的颜色不产生初始费用;若最终落点是黑色,则这次落地也要计数。可以绕行,也可以多次经过同一结点。
输入格式
第一行一个整数 。每组第一行两个整数 ,第二行一个长度为 的二进制串 ,接下来 行,每行两个整数 表示一条无向边。
,,,,。输入图为树;所有组的 之和不超过 。
输出格式
每组输出一行 个整数,依次为到结点 的答案。当 时,该组输出空行。
样例输入
2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9
样例输出
0 1 1 2
1 1 1 0 1 1 1 2