8626: Counting Stickmen
题目描述
In this question, we define the stick man as shown in the picture above. It has a chain of length 1 as the head, two chains of length 2 as the arms, a chain of length 1 as the body, and two chains of length 11 as the legs. For example, the red part in this picture can be viewed as a stick man, with chain (2,3) to be the head, chains (3,4,6) and (3,9,10) to be the arms, chain (3,5) to be the body, and chains (5,7) and (5,8) to be the legs.
The game can be viewed as a tree, and Namesolo wants to know how many stickmen are there. Please note that two stickmen are different when there is at least one different edge between the two edge sets that make up the two stickmen.
Because the answer may be too large, Namesolo wants to know the answer modulo 998244353.
输入格式
The first line of input contains one integer T (1≤T≤15), indicating the number of test cases.
For each test case, the first line contains an integer n 1≤n≤5×105), indicating the number of vertices in the tree. Each of the following n-1 lines contains two integers a,b 1≤a,b≤n), indicating that there is an edge connecting a and b in the tree.
It is guaranteed that the sum of n over all cases won't exceed 3×106.
输出格式
输入样例 复制
1
9
1 2
2 3
3 4
2 5
5 6
2 7
7 8
7 9输出样例 复制
1