Маленький H играет в игру.
Это игра по строительству городов, в которой есть $n$ городов.
Чтобы обеспечить связь между городами, маленький H соединил их $n-1$ ребром. Для каждого ребра $(x, y)$ гарантируется, что города $x$ и $y$ могут обмениваться информацией напрямую. Благодаря этим ребрам любые два города могут обмениваться информацией напрямую или косвенно.
Нетрудно заметить, что у такого подхода есть недостатки. Чем больше промежуточных узлов требуется для передачи сообщения между двумя городами, тем больше времени занимает каждая отправка. Это приводит к тому, что одни города имеют удобную связь, а другие — нет.
Однако увеличение количества ребер приводит к проблемам, с которыми маленький H не может справиться. Чтобы решить это противоречие, маленький H придумал способ: через фиксированные промежутки времени он случайным образом перестраивает сеть. Таким образом, математическое ожидание времени связи между любыми двумя городами становится одинаковым.
Тем не менее, перестройка сети требует затрат. Предположим, что исходная сеть — это $T_1$, а новая сеть — $T_2$. Если у двух сетей есть $x$ общих ребер, то при настройке маленький H может игнорировать эти ребра.
Естественно, чем больше ребер можно игнорировать, тем лучше, поэтому маленький H считает, что ценность такого решения равна $x \cdot 2^x$.
Теперь маленький H собирается провести первую перестройку сети. Чему равна сумма ценностей всех возможных вариантов?
Конечно, этот ответ может быть очень большим, поэтому вам нужно найти его значение по модулю $998244353$.
Формальная постановка задачи
Дано дерево $T_1=\{V, E_1\}$, $|V|=n$. Пусть $S$ — множество всех остовных деревьев, которые можно построить на множестве вершин $V$. Вам нужно найти:
$$\left(\sum_{T_2\in S} |E_1\cap E_2|\cdot 2^{|E_1\cap E_2 |}\right) \bmod 998244353 $$
Нетрудно заметить, что $|S|=n^{n-2}$.
Входные данные
В первой строке содержится целое число $n$.
Далее следуют $n-1$ строк, каждая из которых содержит два целых числа $x_i, y_i$, описывающих ребро в $T_1$.
Выходные данные
Выведите одну строку, содержащую сумму ценностей по модулю $998244353$.
Примеры
Пример 1
Входные данные:
4 1 2 2 3 3 4
Выходные данные:
94
Примечание к примеру 1
Для остовного дерева, содержащего $3$ ребра, существует только $1$ вариант. Следовательно, вклад составляет $3\times 2^3=24$.
Для остовных деревьев, содержащих $2$ ребра, рассмотрим случаи. Если не выбрано $(1,2)$ или $(3,4)$, то существует по $2$ варианта для каждого. Если не выбрано $(2,3)$, то существует $3$ варианта. Следовательно, вклад составляет $7\times 2 \times 2^2=56$.
Для остовных деревьев, содержащих $1$ ребро, если выбрано $(1,2)$ или $(3,4)$, то существует по $2$ варианта для каждого. Если выбрано $(2,3)$, то существует $3$ варианта. Следовательно, вклад составляет $7\times 2=14$.
Ответ: $24+56+14=94$.
Подзадачи
Задача оценивается по системе с группировкой тестов.
Для всех данных выполняется $1 \le n \le 2\times 10^6$.
Подзадачи приведены в таблице ниже:
| Номер подзадачи | $n$ | Особое свойство | Баллы |
|---|---|---|---|
| $1$ | $\le 80$ | Нет | $5$ |
| $2$ | $\le 300$ | Нет | $5$ |
| $3$ | $\le 3000$ | Особое свойство A | $5$ |
| $4$ | $\le 3000$ | Особое свойство B | $5$ |
| $5$ | $\le 3000$ | Нет | $10$ |
| $6$ | $\le 10^5$ | Особое свойство A | $10$ |
| $7$ | $\le 10^5$ | Особое свойство B | $10$ |
| $8$ | $\le 2\times 10^6$ | Особое свойство A | $10$ |
| $9$ | $\le 2\times 10^6$ | Особое свойство B | $10$ |
| $10$ | $\le 2\times 10^6$ | Нет | $30$ |
Особые свойства в таблице:
- Особое свойство A: граф является цепью.
- Особое свойство B: граф является звездой.
Примечание
Объем входных данных в этой задаче велик, пожалуйста, используйте быстрые методы ввода.