33OJ
登录 注册

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

[JAG 2026 Summer Camp #1] Maximum Diameter

题目描述

设 X=(x1,x2,…,xn−1)X=(x_1,x_2,\ldots,x_{n-1}) 是任意一个长度为 n−1n-1、元素均在 11 到 nn 之间(含两端)的整数序列。考虑所有满足以下条件的树。这样的树一定存在。定义 f(X)f(X) 为这些树的直径的最大值。

  • 树有 nn 个节点,编号为 11 到 nn。边的编号为 11 到 n−1n-1。对于每个 ii(1≤i≤n−11\le i\le n-1),第 ii 条边的一个端点为 xix_i。

这里,树的直径是任意两个节点之间的路径所包含的边数的最大值。

给定两个整数序列 A=(a1,a2,…,an−1)A=(a_1,a_2,\ldots,a_{n-1}) 和 B=(b1,b2,…,bn−1)B=(b_1,b_2,\ldots,b_{n-1})。AA 的每个元素均在 11 到 nn 之间(含两端),BB 的每个元素均为正数。保证二元组 (a1,b1),(a2,b2),…,(an−1,bn−1)(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1}) 两两不同。

对于每个 d=2,3,…,n−1d=2,3,\ldots,n-1,解决以下问题:

选择一个整数序列 X=(x1,x2,…,xn−1)X=(x_1,x_2,\ldots,x_{n-1}),使得其元素均在 11 到 nn 之间(含两端),并且满足 f(X)=df(X)=d。这样的序列一定存在。对于每个 ii(1≤i≤n−11\le i\le n-1),当且仅当 xi≠aix_i\ne a_i 时,你需要支付 2bi2^{b_i} 的代价。求总共需要支付的最小代价。

由于每个答案可能很大,输出其对 998 244 353998\,244\,353 取模的结果。

输入格式

输入包含一组测试数据,格式如下:

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

第一行包含一个整数 nn(3≤n≤2×1053\le n\le 2\times 10^5)。第二行包含序列 AA 中的 n−1n-1 个整数(1≤ai≤n1\le a_i\le n)。第三行包含序列 BB 中的 n−1n-1 个整数(1≤bi≤1091\le b_i\le 10^9)。保证当 i≠ji\ne j 时,(ai,bi)≠(aj,bj)(a_i,b_i)\ne(a_j,b_j)。

输出格式

输出 n−2n-2 行。第 kk 行应包含 d=k+1d=k+1 时的答案,即满足 f(X)=k+1f(X)=k+1 的序列 XX 所需的最小总代价对 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