#P18136. Roars III

Roars III

Roars III

在一棵有 nn 个顶点的树中,初始时某些顶点里有一只雄性吼叫蜗牛,每个顶点至多一只。

雌性蜗牛会出现在某个顶点并开始吼叫。只要存在能移动的雄性,每次吼叫会让其中恰好一只沿一条边移动到相邻顶点,并必须满足:

  • 移动方向必须是朝向雌性所在顶点的方向;
  • 目标顶点当前没有其他雄性蜗牛;
  • 已经与雌性位于同一个顶点的雄性不能再移动;其他雄性可以移入尚未被雄性占据的雌性顶点。

当某次吼叫后没有任何雄性蜗牛能够移动时,雌性停止吼叫。雄性蜗牛的移动方式会选择使得吼叫次数最多。

请对每个可能的雌性位置,求出最多能够吼叫多少次。

没有雄性能够移动时过程结束;不能额外给答案加上一次“未引发移动”的吼叫。

输入格式

第一行包含整数 nn(1≤n≤2⋅1051\le n\le2\cdot10^5)。

第二行包含一个长度为 nn 的 0/1 串。若第 ii 个字符为 1,则初始时第 ii 个顶点有一只雄性蜗牛。

接下来 n−1n-1 行,每行包含两个整数 ai,bia_i,b_i,表示一条树边。

输出格式

输出 nn 个整数。第 ii 个整数表示雌性位于第 ii 个顶点时的最大吼叫次数。

样例

5
10101
1 2
2 3
2 4
4 5
2 2 2 3 3

初始树与雄性位置:

样例树

雌性位于 1 时,一种最优过程:

雌性位于 1

雌性位于 4 时,一种最优过程:

雌性位于 4