Background

Systematic conclusions can produce mechanical derivations with a “low level of conjecture,” but more problems require inspiration with a “high level of conjecture.”

— command_block, "Pre-exam Tips".

A mindless contestant chooses a thinking problem.

Problem Description

You need to help djy build a tree that satisfies the following conditions:

• It consists of $n$ nodes.
• The degree of node $i$ is $a_i$.

Define the value of an edge $(i,j)$ as $b_i \times b_j$. Under the conditions above, you need to maximize the sum of values over all edges.

It is guaranteed that such a tree exists.

Input Format

The first line contains an integer $type$, indicating the method of generating the data.

If $type = 0$:

• The second line contains an integer $n$.
• The third line contains $n$ integers, where the $i$-th integer is $a_i$.
• The fourth line contains $n$ integers, where the $i$-th integer is $b_i$.

If $type = 1$:

A data generator template is given:

int a[10000005],b[10000005];
unsigned seed;
unsigned rnd(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return x;
}
int rad(int x,int y){
	seed=rnd(seed);
	return seed%(y-x+1)+x;
}
void init_data(){
	cin>>n>>seed;
	for(int i=1;i<=n;i++)
		a[i]=1,b[i]=rad(1,500000);
	for(int i=1;i<=n-2;i++)
		a[rad(1,n)]++;
}

• The second line contains an integer $n$.
• Then call init_data().
• The third line contains an integer $seed$.

Output Format

Output one integer $ans$ in a single line, representing the maximum possible sum of values.

0
5
1 2 3 1 1 
5 3 1 7 9

42

1
10
114514

249899101316

Hint

This problem uses bundled testing.

• Subtask 0 (10 pts): $n \le 6$, $type = 0$.
• Subtask 1 (20 pts): $n \le 10^3$, $type = 0$.
• Subtask 2 (10 pts): $n \le 5 \times 10^5$, $b_i \le 2$, $type = 0$.
• Subtask 3 (20 pts): $n \le 10^5$, $type = 0$.
• Subtask 4 (20 pts): $n \le 5 \times 10^5$, $type = 0$.
• Subtask 5 (20 pts): $type = 1$.

For $100\%$ of the testdata, $2 \le n \le 10^7$, $1 \le a_i \le n$, $1 \le b_i \le 5 \times 10^5$, $type \in \{0,1\}$, and $0 \le seed < 2^{31}$.

Translated by ChatGPT 5