P16554 [ICPC 2026 LAC] Holes and Tunnels

Path-Digging Animals (PDA) is a new cooperative game for two players that is gaining popularity among programmers. The game is played on a board having $N$ holes and $N-1$ bidirectional tunnels. The tunnels form an undirected tree, which means that there is a unique simple path between each pair of holes. A *route* in PDA is a simple path between **two different holes**. Since tunnels are bidirectional, the direction of a route is not relevant: the (unique) route from hole $U$ to hole $V$ and the (unique) route from hole $V$ to hole $U$ are the same route. Players use animal-shaped pieces for playing PDA. In each round of the game, each player independently chooses a route which is traversed by their animal, and both players score as many points as the number of tunnels that their routes have in common. Right now Alicia and Bruno are at a board game party in Chile playing PDA, and they want to analyze their scoring possibilities. They would like to know, for each integer $k$ from $1$ to $N-1$, how many **ordered** pairs of routes $(A, B)$ there are such that Alicia and Bruno score exactly $k$ points if Alicia chooses route $A$ and Bruno chooses route $B$.

The first line contains an integer $N$ ($2 \le N \le 2 \times 10^5$) indicating the number of holes. Each hole is identified by a distinct integer from $1$ to $N$. Each of the next $N-1$ lines contains two integers $U$ and $V$ ($1 \le U, V \le N$ and $U \neq V$), representing that there is a bidirectional tunnel between holes $U$ and $V$. It is guaranteed that the tunnels form an undirected tree.

Output a single line with $N-1$ integers $P_1, P_2, \dots, P_{N-1}$, where $P_k$ indicates the number of ordered pairs of routes $(A, B)$ such that Alicia and Bruno score exactly $k$ points if Alicia chooses route $A$ and Bruno chooses route $B$. Because these numbers can be very large, output the remainder of dividing each of them by $998244353$.

**Explanation of Sample 1:** There are three possibilities for Alicia's route $A$: the route between holes $1$ and $3$ (formed by the single tunnel between these holes), the route between holes $2$ and $3$ (again a single tunnel), and the route between holes $2$ and $1$ (containing both tunnels). The same three possibilities are available for Bruno's route $B$. The table below shows the score for each combination. As can be seen, $6$ ordered pairs of routes yield a score of $1$ point, while $1$ pair gives $2$ points. Applying the modulo operation does not change these results. :::align{center}  :::