#P17663. [JAG 2026 Summer Camp #1] Maximum Diameter
[JAG 2026 Summer Camp #1] Maximum Diameter
P17526
题目描述
设 是任意一个长度为 、元素均在 到 之间(含两端)的整数序列。考虑所有满足以下条件的树。这样的树一定存在。定义 为这些树的直径的最大值。
- 树有 个节点,编号为 到 。边的编号为 到 。对于每个 (),第 条边的一个端点为 。
这里,树的直径是任意两个节点之间的路径所包含的边数的最大值。
给定两个整数序列 和 。 的每个元素均在 到 之间(含两端), 的每个元素均为正数。保证二元组 两两不同。
对于每个 ,解决以下问题:
选择一个整数序列 ,使得其元素均在 到 之间(含两端),并且满足 。这样的序列一定存在。对于每个 (),当且仅当 时,你需要支付 的代价。求总共需要支付的最小代价。
由于每个答案可能很大,输出其对 取模的结果。
输入格式
输入包含一组测试数据,格式如下:
n
a_1 a_2 ... a_{n-1}
b_1 b_2 ... b_{n-1}
第一行包含一个整数 ()。第二行包含序列 中的 个整数()。第三行包含序列 中的 个整数()。保证当 时,。
输出格式
输出 行。第 行应包含 时的答案,即满足 的序列 所需的最小总代价对 取模的结果。
输入输出样例 #1
输入 #1
5
2 4 3 4
1 2 4 8
输出 #1
18
2
0
输入输出样例 #2
输入 #2
10
6 2 1 6 10 4 6 10 4
1 1 7 8 1 5 5 5 10
输出 #2
454
196
68
36
4
2
0
2
输入输出样例 #3
输入 #3
9
1 1 1 1 1 1 1 1
24 27 30 33 36 39 42 45
输出 #3
0
16777216
150994944
226492415
830472183
671088562
394263947