P17526 [JAG 2026 Summer Camp #1] Maximum Diameter

Let $X=(x_1,x_2,\ldots,x_{n-1})$ be any integer sequence of length $n-1$ whose elements are between $1$ and $n$, inclusive. Consider all trees satisfying the following condition. At least one such tree always exists. Define $f(X)$ as the maximum diameter among these trees. - The tree consists of $n$ nodes numbered $1$ through $n$. Edges are numbered $1$ through $n-1$. For each $i$ ($1\le i\le n-1$), one of the endpoints of edge $i$ is $x_i$. Here, the diameter of a tree is the maximum number of edges on a path between two nodes. You are given two integer sequences, $A=(a_1,a_2,\ldots,a_{n-1})$ and $B=(b_1,b_2,\ldots,b_{n-1})$. Each element in $A$ is between $1$ and $n$, inclusive. Each element in $B$ is positive. You can assume that the pairs $(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1})$ are distinct. For each $d=2,3,\ldots,n-1$, solve the following problem: > Choose an integer sequence $X=(x_1,x_2,\ldots,x_{n-1})$ whose elements are between $1$ and $n$, inclusive, and that satisfies $f(X)=d$. Such a sequence always exists. For each $i$ ($1\le i\le n-1$), you pay a cost of $2^{b_i}$ if and only if $x_i\ne a_i$. Find the minimum possible total cost. Because each answer may be large, output it modulo $998\,244\,353$.

The input consists of a single test case of the following format. ```text n a_1 a_2 ... a_{n-1} b_1 b_2 ... b_{n-1} ``` The first line contains an integer $n$ ($3\le n\le 2\times 10^5$). The second line contains $n-1$ integers in the sequence $A$ ($1\le a_i\le n$). The third line contains $n-1$ integers in the sequence $B$ ($1\le b_i\le 10^9$). It is guaranteed that $(a_i,b_i)\ne(a_j,b_j)$ if $i\ne j$.

Output $n-2$ lines. The $k$-th line should contain the answer for $d=k+1$, i.e., the minimal possible total cost for a sequence $X$ such that $f(X)=k+1$, modulo $998\,244\,353$.