| Когнитивные технологии. Финал 2024 |
|---|
| Finished |
Дано дерево, состоящее из $$$n$$$ вершин, пронумерованных числами от $$$1$$$ до $$$n$$$. У каждой вершины $$$v$$$ кроме корневой непосредственный предок равен $$$p_v$$$, если $$$v$$$ — корень, то выполняется $$$p_v = v$$$. Вершина $$$u$$$ называется предком $$$v$$$, если $$$u$$$ содержится на простом пути от $$$v$$$ до корня дерева. В частности, сама вершина, ее непосредственный предок и корень всегда являются ее предками.
Пусть $$$S$$$ — некоторое множество вершин дерева, обозначим через $$$\textrm{LCA}(S)$$$ наименьшего общего предка множества $$$S$$$, то есть наиболее удаленную от корня вершину, которая является предком для каждой вершины из $$$S$$$.
Например, пусть дерево состоит из $$$6$$$ вершин и имеет вид как на картинке выше. Тогда:
- $$$\textrm{LCA}(\{2, 3\}) = 5$$$
- $$$\textrm{LCA}(\{6, 1\}) = 1$$$
- $$$\textrm{LCA}(\{5, 2, 3\}) = 5$$$
- $$$\textrm{LCA}(\{3\}) = 3$$$
Требуется узнать сумму значений номеров наименьших общих предков для всех непустых подмножеств вершин дерева. Так как ответ может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$
Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество вершин в дереве.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — массив предков.
Гарантируется, что массив $$$p$$$ кодирует некоторое корневое дерево, и что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных на отдельной строке выведите единственное число — сумму значений функции $$$\textrm{LCA}$$$ по всем подмножествам вершин дерева по модулю $$$10^9 + 7$$$.
364 5 5 4 4 122 251 1 1 2 3
250 5 44
Первый набор входных данных соответствует дереву из условия.
