A35245.移动

时间限制: 2S
空间限制: 512mb
样例文件: Move

小 T 有一棵 $n$ 个结点的树，初始时每个结点最多只有一枚棋子。

现在有一个结点 $k$ 是根。每次操作你可以选择一个结点，满足该结点有一枚棋子，将这枚棋子移到它的父亲结点上，需要满足它的父亲结点没有棋子，求最多移动次数。

对 $k=1,2,\cdots,n$ 都求出答案。

第一行一个正整数 $n$ 表示树的点数。

第二行一个长度为 $n$ 的 01 字符串 $s$，其中第 $i$ 个字符 $s$ 表示初始时，结点 $i$ 是否有棋子。如果 $s_i$ 为 1，则说明有，否则说明没有。

接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i, v_i$，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。

一行 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个点为根时的最多移动次数。

对于所有的测试数据，保证：

• $1 \leq n \leq 5\times 10^5$；
• 对于任意的 $i(1 \leq i \leq n - 1)$，都有 $1 \leq u_i, v_i \leq n$，且构成一颗合法的树。

测试点编号	$n\le$	特殊性质
$1\sim 3$	$10$	无
$4,5$	$300$	无
$6$	$2000$	无
$7\sim 9$	$7000$	无
$10\sim 12$	$5\times 10^4$	无
$13\sim 16$	$10^5$	无
$17$	$3\times 10^5$	无
$18,19$	$5\times 10^5$	A
$20,21$	$5\times 10^5$	B
$22\sim 24$	$5\times 10^5$	C
$25$	$5\times 10^5$	无

• 特殊性质 A：保证 $\forall i\in [1, n-1]\cap \mathbb{Z}$，满足 $i$ 和 $i+1$ 有边；
• 特殊性质 B：保证 $\forall i\in [2, n]\cap \mathbb{Z}$，满足 $1$ 和 $i$ 有边；
• 特殊性质 C：保证树的生成方式形如，对于结点 $i\in [2,n]$，在 $[1,i-1]$ 内等概率随机一个点 $p$，将 $i,p$ 连一条边。