Background

This is the hard version of the problem. The only difference between the two versions under the $\bm{100 \%}$ testdata constraints is the limit on $\bm{n}$. In this version, $\bm{n \le {10}^6}$.

There are places we long for in dreams, and there are distant places in reality that we can see but can never reach.

We are waiting for countless hopes, for a new era; life has never played its final movement.

In an instant, everything in the upheaval is overturned. The sky falls into the sea, choking every breath of those who live. Wings are wrapped in freezing seawater, sorrowful enough to make one forget the meaning of breathing from that moment on.

Only a hair’s breadth away from the air, yet I no longer want to try to breathe. I begin to understand: when sorrow reaches the extreme, maybe there will be no tears.

The gods, in the name of life, fabricate a gloomy truth.

Tears blur my eyes; my body falls into the sky. The pale daylight has no choice but to light up the hope of this day.

Problem Description

There is now a rooted binary tree with $n$ nodes.

Mortals and gods play a game on this tree. The mortal needs to drop some balls from the root. Each ball carries either $1$ unit of positive charge or $1$ unit of negative charge.

Each node on the tree has a capacity. Node $i$ can hold $c_i$ balls. Initially, every node holds $0$ balls. We say a node is full if and only if the number of balls it holds equals its capacity.

Each time a ball falls onto a node:

• If this node has no child nodes, or all child nodes are already full, then it stops, and the number of balls held by this node increases by $1$;
• If this node has exactly one child node that is not full, then the ball falls to that child;
• If both child nodes are not full:
  • If the algebraic sum of charges of all balls in the left subtree is greater than the algebraic sum of charges of all balls in the right subtree, then if the current ball is positively charged it falls to the right, otherwise it falls to the left;
  • If the algebraic sum of charges of all balls in the left subtree is less than the algebraic sum of charges of all balls in the right subtree, then if the current ball is positively charged it falls to the left, otherwise it falls to the right;
  • If the algebraic sum of charges of all balls in the left subtree equals the algebraic sum of charges of all balls in the right subtree, then the gods decide which direction it falls.

Here, the algebraic sum of charges means the number of positively charged balls minus the number of negatively charged balls.

Before the game starts, both sides agree on a target node $u$. In one round, the mortal chooses the polarity of the ball dropped in this round, and the gods control the falling process according to the rules above. When $u$ becomes full, the game ends.

The mortal wants the number of rounds to be as small as possible, and the gods want the number of rounds to be as large as possible. Assume both sides are smart enough.

For all $1\leq u\leq n$, find the number of rounds $r_u$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n-1$ integers $f_2, f_3, \ldots, f_n$, where $f_i$ is the index of the parent of node $i$.

The third line contains $n$ integers $c_1, c_2, \ldots, c_n$.

Output Format

Output one line with $n$ integers $r_1, r_2, \ldots, r_n$.

5
1 1 2 2
1 1 1 1 1

5 4 2 3 3

Hint

【Constraints】

This problem uses bundled tests.

For $100\%$ of the testdata, $2 \le n \le {10}^6$. The tree is a rooted binary tree with root $1$, and it satisfies $1 \le f_i < i$ and $1 \le c_i \le {10}^{12}$.

【Hint】

The maximum I/O size of this problem reaches 20 MiB. Please pay attention to I/O efficiency.

Translated by ChatGPT 5