Ориентированное дерево Дан неориентированный связный граф без циклов g с n вершинами и n-1 ребром. Другими словами дано дерево на n вершинах.

Получим ориентированный граф g' следующим образом: ориентируем каждое из ребер дерева (то есть для каждого ребра u-v в изначальном графе, в графе g' проведем ориентированное ребро u → v или v → u).

Найдите сумму количеств путей по всем возможным g'. Путем называется последовательность вершин a1, a2, ..., am такая, что для любого i(1 ≤ i ≤ m-1) существует ориентированное ребро ai → ai+1 и ax ≠ ay, если x ≠ y (в частности, существуют пути, состоящие ровно из одной вершины). Так как ответ может быть достаточно большим, выведите его по модулю 109 + 7.

Формат входных данных
В первой строке задано одно целое число n (1 ≤ n ≤ 106) - количество вершин в изначальном графе.

В каждой из последующих n-1 строк содержится по два целых числа u и v (1 ≤ u, v ≤ n, u ≤ v) - две вершины, которые соединены ребром. Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра.

Танюша9102    2   11.11.2021 03:39    4