题目描述
设 X=(x1,x2,…,xn−1) 是任意一个长度为 n−1、元素均在 1 到 n 之间(含两端)的整数序列。考虑所有满足以下条件的树。这样的树一定存在。定义 f(X) 为这些树的直径的最大值。
- 树有 n 个节点,编号为 1 到 n。边的编号为 1 到 n−1。对于每个 i(1≤i≤n−1),第 i 条边的一个端点为 xi。
这里,树的直径是任意两个节点之间的路径所包含的边数的最大值。
给定两个整数序列 A=(a1,a2,…,an−1) 和 B=(b1,b2,…,bn−1)。A 的每个元素均在 1 到 n 之间(含两端),B 的每个元素均为正数。保证二元组 (a1,b1),(a2,b2),…,(an−1,bn−1) 两两不同。
对于每个 d=2,3,…,n−1,解决以下问题:
选择一个整数序列 X=(x1,x2,…,xn−1),使得其元素均在 1 到 n 之间(含两端),并且满足 f(X)=d。这样的序列一定存在。对于每个 i(1≤i≤n−1),当且仅当 xi=ai 时,你需要支付 2bi 的代价。求总共需要支付的最小代价。
由于每个答案可能很大,输出其对 998244353 取模的结果。
输入格式
输入包含一组测试数据,格式如下:
n
a_1 a_2 ... a_{n-1}
b_1 b_2 ... b_{n-1}
第一行包含一个整数 n(3≤n≤2×105)。第二行包含序列 A 中的 n−1 个整数(1≤ai≤n)。第三行包含序列 B 中的 n−1 个整数(1≤bi≤109)。保证当 i=j 时,(ai,bi)=(aj,bj)。
输出格式
输出 n−2 行。第 k 行应包含 d=k+1 时的答案,即满足 f(X)=k+1 的序列 X 所需的最小总代价对 998244353 取模的结果。
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