6599: Counting Stickmen
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Namesolo has fallen in love with the game Stick Fight. But when he is playing the game, he wonders how to find out the number of stickmen in the game.
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 1 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.
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 1 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.
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.
输出
For each test case, output an integer representing the answer modulo 998244353.
样例输入 复制
1
9
1 2
2 3
3 4
2 5
5 6
2 7
7 8
7 9样例输出 复制
1