Саша хочет прогуляться со своей девушкой по городу. Город состоит из n перекрёстков, пронумерованных от 1 до n. Некоторые из них соединены дорогами, причём от любого перекрёстка существует ровно один простой путь† до любого другого перекрёстка. Другими словами, перекрёстки и дороги между ними образуют дерево.
Некоторые из перекрёстков являются опасными. И так как гулять одним по городу небезопасно, то Саша не хочет за время прогулки посещать три и более опасных перекрёстков.
Саша называет множество перекрёстков хорошим, если выполняется следующее условие:
Однако Саша не знает, какие из перекрёстков являются опасными, поэтому его интересует количество различных хороших множеств перекрёстков, которые есть в городе. Поскольку это количество может быть очень большим, выведите его по модулю 998244353.
†Простой путь — это путь, проходящий через каждый перекрёсток не более одного раза.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t (1≤t≤104) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число n (2≤n≤3⋅105) — количество перекрёстков в городе.
Следующие (n−1) строка описывают дороги. i-я из них содержит два целых числа ui и vi (1≤ui,vi≤n, ui≠vi) — номера перекрёстков, которые соединяет i-я дорога.
Гарантируется, что данные дороги образуют дерево.
Гарантируется, что сумма n по всем наборам входных данных не превышает 3⋅105.
Для каждого набора входных данных выведите одно целое число — количество хороших множеств перекрёстков по модулю 998244353.
431 33 243 42 33 151 23 45 12 341 22 33 4
7 12 16 11
В первом наборе входных данных всего есть 23=8 множеств перекрёстков. Все из них являются хорошими, кроме множества {1,2,3}, потому что, если перекрёстки 1,2 и 3 являются опасными, то простой путь 1−2−3 содержит 3 опасных перекрёстка. Таким образом, всего есть 7 хороших множеств.
Во втором наборе входных данных всего есть 24=16 множеств перекрёстков. При этом множества {1,2,3,4}, {1,2,3}, {1,3,4}, {2,3,4} не являются хорошими. Таким образом, всего есть 12 хороших множеств. Ниже изображена схема города:
| Codeforces Round 926 (Div. 2) |
|---|
| Закончено |
