406816: GYM102565 E OneZeroTree

It's Christmas time! You and your friends love Christmas, and you decide to go to see the Christmas Tree from your city fair. With this opportunity, you want to show off to your friends your programming skills.

The Christmas Tree can be represented as a Tree with $$$1 \leq N \leq 10^5$$$ vertices indexed from $$$1$$$ to $$$N$$$ (a connected graph with $$$N$$$ vertices and $$$N-1$$$ edges). Each node can be turned on or turned off. A configuration is defined as a simple path from vertex $$$x$$$ to vertex $$$y$$$ ($$$x \leq y$$$) in which every vertex can be turned on or off. Two configurations are different if their associated paths are different or if there is at least one vertex that has different states in the two configurations (i.e., it is turned on in one configuration and turned off in the other one). The cost of a configuration is the number of vertices that are turned on.

For each $$$k$$$ from $$$0$$$ to $$$N$$$, you need to find out the number of configurations of cost equal to $$$k$$$. Because this number can be very large, you need to compute it modulo $$$998244353$$$.

The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of vertices of the Tree. The following $$$N-1$$$ lines will contain two numbers $$$x_i$$$ ($$$1 \leq x_i \leq N$$$) and $$$y_i$$$ ($$$1 \leq y_i \leq N$$$) each, representing an edge between $$$x_i$$$ and $$$y_i$$$.

You should output one line consisting of $$$N+1$$$ numbers, representing the answer for each $$$k$$$ from $$$0$$$ to $$$N$$$, in this order.

4
1 2
2 3
2 4

10 19 12 3 0 

For k = 2 :

the path from 1 to 1 has 0 ways of turning on 2 vertices

the path from 2 to 2 has 0 ways of turning on 2 vertices

the path from 3 to 3 has 0 ways of turning on 2 vertices

the path from 4 to 4 has 0 ways of turning on 2 vertices

the path from 1 to 2 has 1 way of turning on 2 vertices

the path from 1 to 3 has 3 ways of turning on 2 vertices

the path from 1 to 4 has 3 ways of turning on 2 vertices

the path from 2 to 3 has 1 way of turning on 2 vertices

the path from 2 to 4 has 1 way of turning on 2 vertices

the path from 3 to 4 has 3 ways of turning on 2 vertices

In total there are 12 configurations with cost 2.