| Codeforces Round 1024 (Div. 1) |
|---|
| Закончено |
Вам дано дерево с $$$n$$$ вершинами, где каждая вершина может быть покрашена в красный, синий или белый цвет. Крутость раскраски определяется как максимальное расстояние$$$^{\text{∗}}$$$ между красной и синей вершиной.
Формально, если мы обозначим цвет $$$i$$$-й вершины как $$$c_i$$$, то крутость раскраски равна $$$\max d(u, v)$$$ среди всех пар вершин $$$1\le u, v\le n$$$, где $$$c_u$$$ — красный, и $$$c_v$$$ — синий. Если на дереве нет красных или нет синих вершин, то крутость равна нулю.
Ваша задача — вычислить сумму крутостей всех $$$3^n$$$ возможных раскрасок дерева, по модулю $$$998\,244\,353$$$.
$$$^{\text{∗}}$$$Расстояние между двумя вершинами $$$a$$$ и $$$b$$$ в дереве равно количеству рёбер на уникальном простом пути между вершиной $$$a$$$ и вершиной $$$b$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 3000$$$) — количество вершин в дереве.
Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u, v\le n$$$) — концы рёбер дерева.
Гарантируется, что заданные рёбра образуют дерево.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.
Для каждого набора входных данных выведите сумму крутостей всех $$$3^n$$$ возможных раскрасок дерева, по модулю $$$998\,244\,353$$$.
331 22 361 21 31 43 55 6171 21 31 41 52 62 72 83 93 107 117 1211 1313 1414 1510 1616 17
18 1920 78555509
В первом наборе входных данных есть $$$12$$$ раскрасок, которые имеют хотя бы одну синюю и одну красную вершину. Следующие картинки показывают раскраски и их крутость:
Все эти раскраски имеют крутость $$$2$$$ 
Все эти раскраски имеют крутость $$$1$$$ Таким образом, сумма крутостей среди всех возможных раскрасок равна $$$6\cdot 2 + 6\cdot 1 = 18$$$.
Во втором наборе входных данных приведены некоторые примеры раскрасок с крутостью $$$3$$$:
