33OJ
登录 注册

#P17526. [JAG 2026 Summer Camp #1] Maximum Diameter

[JAG 2026 Summer Camp #1] Maximum Diameter

Problem Description

Let X=(x1,x2,…,xn−1)X=(x_1,x_2,\ldots,x_{n-1}) be any integer sequence of length n−1n-1 whose elements are between 11 and nn, inclusive. Consider all trees satisfying the following condition. At least one such tree always exists. Define f(X)f(X) as the maximum diameter among these trees.

  • The tree consists of nn nodes numbered 11 through nn. Edges are numbered 11 through n−1n-1. For each ii (1≤i≤n−11\le i\le n-1), one of the endpoints of edge ii is xix_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=(a1,a2,…,an−1)A=(a_1,a_2,\ldots,a_{n-1}) and B=(b1,b2,…,bn−1)B=(b_1,b_2,\ldots,b_{n-1}). Each element in AA is between 11 and nn, inclusive. Each element in BB is positive. You can assume that the pairs (a1,b1),(a2,b2),…,(an−1,bn−1)(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1}) are distinct.

For each d=2,3,…,n−1d=2,3,\ldots,n-1, solve the following problem:

Choose an integer sequence X=(x1,x2,…,xn−1)X=(x_1,x_2,\ldots,x_{n-1}) whose elements are between 11 and nn, inclusive, and that satisfies f(X)=df(X)=d. Such a sequence always exists. For each ii (1≤i≤n−11\le i\le n-1), you pay a cost of 2bi2^{b_i} if and only if xi≠aix_i\ne a_i. Find the minimum possible total cost.

Because each answer may be large, output it modulo 998 244 353998\,244\,353.

Input Format

The input consists of a single test case of the following format.

n
a_1 a_2 ... a_{n-1}
b_1 b_2 ... b_{n-1}

The first line contains an integer nn (3≤n≤2×1053\le n\le 2\times 10^5). The second line contains n−1n-1 integers in the sequence AA (1≤ai≤n1\le a_i\le n). The third line contains n−1n-1 integers in the sequence BB (1≤bi≤1091\le b_i\le 10^9). It is guaranteed that (ai,bi)≠(aj,bj)(a_i,b_i)\ne(a_j,b_j) if i≠ji\ne j.

Output Format

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

5
2 4 3 4
1 2 4 8
18
2
0
10
6 2 1 6 10 4 6 10 4
1 1 7 8 1 5 5 5 10
454
196
68
36
4
2
0
2
9
1 1 1 1 1 1 1 1
24 27 30 33 36 39 42 45
0
16777216
150994944
226492415
830472183
671088562
394263947