Sum of Weighted Labels in Valid Tree Topological Orderings

Given a rooted tree with (n) nodes (node 1 is the root) and parent pointer (fa_u) for every node (u) (for (u \ge 2)), and a weight sequence (b_1, b_2, \dots, b_n), we call a permutation (a = (a_1, a_2, \dots, a_n)) of ({1,2,\dots,n}\nvalid if and only if for every (2 \le u \le n), (a_u > a_{fa_u}). For every node (u), define [ f(u) = \sum_{\text{valid } a} b_{a_u}, ] where the sum is taken over all valid topological orderings of the tree. Output (f(u) \bmod (10^9+7)) for every (1 \le u \le n).

It can be shown that the total number of valid labelings is given by the hook‐length formula [ \text{tot} = \frac{n!}{\prod_{u=1}^{n} h_u},] where (h_u) is the size of the subtree rooted at (u). Moreover, observe that in any valid labeling the label assigned to a node (u) is the minimum number among the set of labels assigned to the nodes in the subtree of (u). Thus, if (|T_u|=s) and if the available numbers are from (L+1) to (n) (with parent’s label being (L)), the conditional probability that (a_u=x) is given by [ P(a_u = x \mid a_{fa_u}=L) = \frac{\binom{n-x}{s-1}}{\binom{n-L}{s}},\quad x = L+1,\dots,n-s+1. ] Using this fact and a DFS over the tree one may compute for each node (u) the value of [ f(u) = \text{tot} \cdot \sum_{x=1}^{n} b_x \cdot P(a_u=x), \quad (\bmod\ 10^9+7). ]

Note: It is guaranteed that (n) is small enough so that an (O(n^2)) solution passes. The answer codes below compute the distributions of labels for each node using dynamic programming based on the above observation.

inputFormat

The first line contains an integer \(n\) \( (2 \le n \le 2000)\) which is the number of nodes of the tree.

The second line contains \(n-1\) integers, where the \(i\)-th integer (for \(i=2,3,\dots,n\)) is \(fa_i\) (\(1 \le fa_i < i\)).

The third line contains \(n\) integers \(b_1, b_2, \dots, b_n\) (each between \(1\) and \(10^9\)).

It is guaranteed that the given \(fa_i\) values form a valid tree with node 1 as the root.

outputFormat

Output one line containing \(n\) integers, where the \(u\)-th integer is \(f(u) \bmod (10^9+7)\).

sample

2
1
1 2

1 2