Suffix Extension Profit Sum

You are given a rooted tree of n nodes with root 1. Each edge is labeled with a character from the set \(\{0,1\}\). For every node \(u\), let \(S_u\) be the string formed by concatenating the characters on the unique simple path from the root to \(u\). It is guaranteed that for every node, the characters on the edges to its children are distinct.

In addition, every node \(u\) is assigned a limit \(a_u\) and a value \(\mathit{val}_u\). We say that a node \(v\) is an extension node of node \(u\) if \(S_u\) is a suffix of \(S_v\); in other words, if \[ S_u = S_v[|S_v|-|S_u|+1,\;|S_v|], \] where \(S[l,r]\) denotes the substring of \(S\) from index \(l\) to \(r\) (and by convention \(S[x+1,x]\) is the empty string).

Alice holds a string \(S = S_u\) (for some node \(u\)). She can delete anywhere from \(0\) to \(|S|\) characters from the end of \(S\) to obtain a string \(S'\) (so there are \(|S|+1\) choices). She then reveals \(S'\) to Bob. Upon receiving \(S'\), Bob appends some characters to the end of \(S'\) to form a new string \(S''\). If there is some extension node \(v\) of \(u\) such that

• \(S'' = S_v\),
• \(S_v[1,i] = S_u[1,i]\) (where \(i = |S'|\); we use 1-indexing for strings), and
• \(i \ge a_v\),

then Bob obtains a profit of \(\mathit{val}_v\). Since Bob can perform this operation only once, he will choose the extension node \(v\) that maximizes \(\mathit{val}_v\) among those satisfying the conditions. If no such \(v\) exists, Bob gets a profit of 0 for that deletion.

Alice is curious about the total profit Bob can obtain. More precisely, for each node \(u\), define \[ \mathit{ans}_u = \sum_{i=0}^{|S_u|} \max\Big\{\mathit{val}_v : \;i \ge a_v \;\land\; S_u = S_v[|S_v|-|S_u|+1,|S_v|] \;\land\; S_u[1,i] = S_v[1,i]\Big\}, \] where the maximum is taken over all extension nodes \(v\) of \(u\) satisfying the stated conditions (with the convention that if no such \(v\) exists the maximum is 0). Your task is to compute \(\mathit{ans}_u\) for every node \(u\).

Note: \(S[1,i]\) denotes the prefix of \(S\) of length \(i\), and \(|S|\) denotes the length of \(S\).

inputFormat

The input is given as follows:

1. The first line contains an integer \(n\) (\(1 \le n \le 10^3\)), the number of nodes in the tree.
2. The next \(n-1\) lines each contain a parent index and a character (either 0 or 1). The \(i\)-th of these lines (for \(i\) from 2 to \(n\)) describes the edge from node \(p_i\) to node \(i\) with the given character.
3. The next \(n\) lines each contain two integers \(a_u\) and \(\mathit{val}_u\), for \(u = 1, 2, \dots, n\).

It is guaranteed that for any node, the characters on the edges to its children are distinct.

outputFormat

Output \(n\) integers separated by spaces. The \(u\)-th integer should be \(\mathit{ans}_u\), the total profit Bob can obtain when starting from node \(u\).

sample

1

0 10

10