Background

This is the easy version of the problem. The only difference between the two versions in the $\bm{100 \%}$ testdata constraints is the limit on $\bm{n}$. In this version, $\bm{n \le 1000}$.

There are places longed for in dreams, and there are distant places in reality that can be seen but never reached.

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

In an instant, everything is overturned. The sky falls into the sea, choking every last breath of those who breathe. Wings are wrapped in freezing seawater, and the sorrow is so deep that one forgets the meaning of breathing.

Clearly separated from the air by only a hair’s breadth, yet no longer wanting to try to breathe again. I begin to understand: when sorrow reaches its extreme, perhaps there are no tears.

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

Tears blur the eyes. The 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 several 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, the number of balls in every node is $0$. 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 the node has no children, or all of its children are already full, then it stops: the number of balls held by this node increases by $1$.
• If exactly one child is not full, then the ball falls to that child.
• If both children are not full:
  • If the algebraic sum of charges of all balls in the left subtree is greater than that 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 that 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 sums are equal, then the god decides which direction it falls.

Here, the algebraic sum of charges means (number of positive charges) minus (number of negative charges).

Before the game starts, both sides agree on a target node $u$. In one round, the mortal chooses the charge of the ball dropped this time, and the god controls 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, while the god wants it to be as large as possible. Assume both sides are smart enough.

For all $1\leq u\leq n$, compute 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$ denotes 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 containing $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.

• Special Property A: The tree degenerates into a chain with $1$ as one endpoint.
• Special Property B: $c_i = 1$.

For $100\%$ of the data, $2 \le n \le 1000$. The tree is a binary tree rooted at $1$, $1 \le f_i < i$, and $1 \le c_i \le {10}^{12}$.

Translated by ChatGPT 5