小红的二进制树
题号：NC268127
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一棵有根树，根节点为 1 号节点，其中每个节点有一个二进制数字'0'或者'1'。
现在小红定义f(i)为：从i号节点出发，到某节点停止的路径所对应的二进制数为奇数的路径数量。请你求出f(1),f(2)...f(n)的值。
我们定义路径是只能向孩子出发的，不能往祖先方向走。

输入描述:

第一行输入一个正整数n，代表树的节点数量。
第二行输入一个长度为n的 01 串，第i个字符代表i号节点上的二进制数字。
接下来的n-1行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。
1\leq n \leq 10^5
1\leq u,v \leq n

输出描述:

输出n行，第i行为f(i)的值。
示例1

输入

复制 
3
101
1 2
2 3

输出

复制 
1
1
0

说明

从 1 号节点出发，合法的路径有 1 条：1->2->3。
从 2 号节点出发，合法的路径有 1 条：2->3。
从 3 号节点出发，显然不存在合法的路径，因为 3 号节点是叶子节点。