Задача №114673. Древо жизни
Всего есть \(n\) возможных событий, счастье от наступления \(i\)-го события равно \(a_i\). Событие называется радостным, если \(a_i \ge 0\). Рассмотрим произвольную расстановку событий в древе жизни, где каждой вершине соответствует ровно одно событие, каждое событие соответствует какой-либо вершине. Справедивостью судьбы назвовем суммарное счастье событий, достижимых в дереве из корня, если разрешено перемещаться только по радостным событиям. Иначе говоря, таких событий, что существует путь из корня в вершину с этим событием, проходящий только по радостным событиям. Требуется просуммировать справедливость судьб по всем возможным способам расставить события в вершинах дерева. Две расстановки считаются различными, если существует вершина дерева, которой соответствуют события с разными номерами.
Так как ответ может быть очень большим, посчитайте его по модулю \(10^9 + 7\).
В первой строке входных данных содержится целое число \(n\) (\(2 \leq n \leq 200\,000\)) — количество вершин в дереве судьбы и количество событий.
В следующей строке содержится \(n-1\) целое число \(p_2,\ p_3,\ p_4,\ \ldots\ p_n\) (\(1 \leq p_i < i\)), где \(p_i\) — предок \(i\)-й вершины в дереве судьбы. Корнем дерева судьбы является вершина номер \(1\).
В следующей строке содержится \(n\) целых чисел \(a_i\) (\(|a_i| \leq 10^9\)) — счастье от наступления каждого события.
Выведите единственное целое число — искомую сумму по модулю \(10^9 + 7\).
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 15 | \(n \le 10\) | 0 | |
| 2 | 10 | \(n \le 20\) | 0, 1 | |
| 3 | 12 | – | – | \(p_i = 1\) |
| 4 | 16 | \(n \le 200\) | 0, 1, 2 | |
| 5 | 13 | \(n \leq 2000\) | – | \(p_i = i - 1\) |
| 6 | 15 | – | 5 | \(p_i = i - 1\) |
| 7 | 19 | – | 0–6 |
3 1 1 1 2 -1
12
4 1 2 1 2 0 3 1
144
7 1 1 2 1 2 3 4 -1 2 0 -3 9 -1
33480