P10013 [CTT Mutual Test 2023] Tree Topological Order Counting

Given a rooted tree with $n$ nodes, where node $1$ is the root, let the parent of $u$ be $fa_u$. You are also given a weight sequence $b$ of length $n$. A permutation $a$ of length $n$ is called a valid topological order of this tree if and only if $\forall 2 \le u \le n, a_u > a_{fa_u}$. For each node $u$, define $f(u)$ as the sum of $b_{a_u}$ over all valid topological orders of this tree. Now, for $1 \le u \le n$, compute $f(u) \bmod 10^9+7$.

The first line contains an integer $n$, the number of nodes in the tree. The second line contains $n-1$ integers. The $i$-th integer denotes $fa_{i+1}$, describing the structure of the tree. The third line contains $n$ integers. The $i$-th integer denotes $b_i$, describing the weight sequence.

Output one line with $n$ integers. The $i$-th integer denotes $f(i) \bmod 10^9+7$.

| Subtask | $n \le$ | Special Constraint | Score | | :-----: | :-----: | :----------------: | :---: | | $1$ | $10$ | None | $5$ | | $2$ | $20$ | None | $10$ | | $3$ | $100$ | None | $15$ | | $4$ | $350$ | None | $15$ | | $5$ | $3000$ | A | $15$ | | $6$ | $3000$ | None | $20$ | | $7$ | $5000$ | None | $20$ | Special constraint A: $\forall 1 \le i \le n, b_i = i$. Constraints for all testdata: $2 \le n \le 5000$, $1 \le fa_i < i$, $0 \le b_i < 10^9+7$. Translated by ChatGPT 5