Определим ранг неориентированного графа как ранг его матрицы смежности в $$$\mathbb{R}^{n \times n}$$$.
Дано дерево. Каждое из рёбер дерева исчезает с вероятностью $$$1/2$$$ независимо от остальных. Пусть $$$E$$$ — математическое ожидание ранга полученного леса. Найдите остаток от деления $$$E \cdot 2^{n-1}$$$ на $$$998244353$$$ (несложно показать, что $$$E \cdot 2^{n-1}$$$ — целое число).
В первой строке записано одно число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — количество вершин дерева.
В следующих $$$n-1$$$ строках описаны рёбра дерева. Каждое ребро описывается парой $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) вершин, которые оно соединяет.
Гарантируется, что описанный граф является деревом.
Выведите одно число — ответ на задачу.
3
1 2
2 3
6
4
1 2
1 3
1 4
14
4
1 2
2 3
3 4
18
Название |
---|