#P17526. [JAG 2026 Summer Camp #1] Maximum Diameter
[JAG 2026 Summer Camp #1] Maximum Diameter
Problem Description
Let be any integer sequence of length whose elements are between and , inclusive. Consider all trees satisfying the following condition. At least one such tree always exists. Define as the maximum diameter among these trees.
- The tree consists of nodes numbered through . Edges are numbered through . For each (), one of the endpoints of edge is .
Here, the diameter of a tree is the maximum number of edges on a path between two nodes.
You are given two integer sequences, and . Each element in is between and , inclusive. Each element in is positive. You can assume that the pairs are distinct.
For each , solve the following problem:
Choose an integer sequence whose elements are between and , inclusive, and that satisfies . Such a sequence always exists. For each (), you pay a cost of if and only if . Find the minimum possible total cost.
Because each answer may be large, output it modulo .
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 (). The second line contains integers in the sequence (). The third line contains integers in the sequence (). It is guaranteed that if .
Output Format
Output lines. The -th line should contain the answer for , i.e., the minimal possible total cost for a sequence such that , modulo .
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