CF1930G Prefix Max Set Counting

Define a function $ f $ such that for an array $ b $ , $ f(b) $ returns the array of prefix maxima of $ b $ . In other words, $ f(b) $ is an array containing only those elements $ b_i $ , for which $ b_i=\max(b_1,b_2,\ldots,b_i) $ , without changing their order. For example, $ f([3,10,4,10,15,1])=[3,10,10,15] $ . You are given a tree consisting of $ n $ nodes rooted at $ 1 $ . A permutation $ ^\dagger $ $ p $ of is considered a pre-order of the tree if for all $ i $ the following condition holds: - Let $ k $ be the number of proper descendants $ ^\ddagger $ of node $ p_i $ . - For all $ x $ such that $ i < x \leq i+k $ , $ p_x $ is a proper descendant of node $ p_i $ . Find the number of distinct values of $ f(a) $ over all possible pre-orders $ a $ . Since this value might be large, you only need to find it modulo $ 998\,244\,353 $ . $ ^\dagger $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^\ddagger $ Node $ t $ is a proper descendant of node $ s $ if $ s \neq t $ and $ s $ is on the unique simple path from $ t $ to $ 1 $ .

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^6 $ ) — the number of vertices. The following next $ n-1 $ lines contain two integers $ u $ and $ v $ ( $ 1 \leq u, v \leq n $ , $ u \neq v $ ) — denoting an edge between nodes $ u $ and $ v $ . It is guaranteed that the given edges form a tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output the number of distinct values of $ f(a) $ modulo $ 998\,244\,353 $ that you can get.

In the first test case, the only valid pre-order is $ a=[1] $ . So the only possible value of $ f(a) $ is $ [1] $ . In the second test case, the only valid pre-order is $ a=[1,2] $ . So the only possible value $ f(a) $ is $ [1,2] $ . In the third test case, the two valid pre-orders are $ a=[1,2,3] $ and $ a=[1,3,2] $ . So the possible values of $ f(a) $ are $ [1,2,3] $ and $ [1,3] $ . In the fifth test case, the possible values of $ f(a) $ are: - $ [1,5] $ ; - $ [1,2,5] $ ; - $ [1,3,5] $ ; - $ [1,4,5] $ ; - $ [1,2,3,5] $ ; - $ [1,2,4,5] $ ; - $ [1,3,4,5] $ ; - $ [1,2,3,4,5] $ .