CF1667E Centroid Probabilities

Consider every tree (connected undirected acyclic graph) with $ n $ vertices ( $ n $ is odd, vertices numbered from $ 1 $ to $ n $ ), and for each $ 2 \le i \le n $ the $ i $ -th vertex is adjacent to exactly one vertex with a smaller index. For each $ i $ ( $ 1 \le i \le n $ ) calculate the number of trees for which the $ i $ -th vertex will be the centroid. The answer can be huge, output it modulo $ 998\,244\,353 $ . A vertex is called a centroid if its removal splits the tree into subtrees with at most $ (n-1)/2 $ vertices each.

N/A

N/A

Example $ 1 $ : there are two possible trees: with edges $ (1-2) $ , and $ (1-3) $ — here the centroid is $ 1 $ ; and with edges $ (1-2) $ , and $ (2-3) $ — here the centroid is $ 2 $ . So the answer is $ 1, 1, 0 $ . Example $ 2 $ : there are $ 24 $ possible trees, for example with edges $ (1-2) $ , $ (2-3) $ , $ (3-4) $ , and $ (4-5) $ . Here the centroid is $ 3 $ .