题目背景

这是本题的困难版本。两个版本在 $\bm{100 \%}$ 数据范围的唯一区别是关于 $\bm{n}$ 的限制。此版本中 $\bm{n \le {10}^6}$。

---

有梦中所向往的地方，也有现实中可望不可触及的远方。

我们正等待无数次的希望，新的纪元，生命不曾奏响终章。

顷刻间颠覆中的一切，天空坠落到海底，死死卡住呼吸者的全部。羽翼裹满刺骨的海水，悲伤到从此遗忘呼吸的意义。

明明与空气只隔着毫厘，却不想再尝试去呼吸。我开始明白，悲伤到了极点，也许不会流泪

神明借着生的名义，捏造出灰暗的真理。

泪水模糊眼眶，身躯坠进天空，泛白的天光，不得已照亮这一日的希望。

题目描述

现在有一棵 $n$ 个节点的有根二叉树。

凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带 $1$ 单位正电荷或带 $1$ 单位负电荷。

树上每一个点有容量，第 $i$ 个点可以容纳 $c_i$ 个球。初始每一个点容纳的球数为 $0$。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。

每一次一个球下落到一个点时：

• 如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数 $+1$；
• 如果该点恰有一个孩子节点未充满，则向那个孩子下落；
• 如果有 $2$ 个孩子节点均未充满：
  • 如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落；
  • 如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；
  • 如果左侧子树中所有球的电荷代数和等于右侧子树所有球的电荷代数和，则由神明决定向哪个方向下落。

其中，电荷代数和指的是正电荷的数量减去负电荷的数量。

在游戏开始前，双方约定目标点 $u$。在一个回合中，凡人选择这次投下的球的电性，神明按上述规则控制球的下落过程。当 $u$ 被充满时，游戏结束。

凡人希望游戏回合数尽量少，神明希望游戏回合数尽量多。假设双方足够聪明。

对所有：$1\leq u\leq n$，求游戏轮数 $r_u$。

输入格式

第一行，一个正整数 $n$。

第二行，$n-1$ 个整数 $f_2, f_3, \ldots, f_n$，其中 $f_i$ 代表 $i$ 的父亲的编号。

第三行，$n$ 个整数 $c_1, c_2, \ldots, c_n$。

输出格式

输出一行，$n$ 个整数 $r_1, r_2, \ldots, r_n$。

5
1 1 2 2
1 1 1 1 1

5 4 2 3 3

提示

【数据范围】

本题采用捆绑测试。

子任务编号	$n \le$	分值
4	${10}^5$	33
5	${10}^6$	67

对于 $100\%$ 的数据，$2 \le n \le {10}^6$，满足树是以 $1$ 为根的二叉树，$1 \le f_i < i$，$1 \le c_i \le {10}^{12}$。

---

【提示】

本题最大 I/O 量达到 20 MiB，请注意 I/O 效率。