P7390 "EZEC-6" Building a Tree.

> 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". [](https://cdn.luogu.com.cn/upload/image_hosting/1m9hce9x.png)A mindless contestant chooses a thinking problem.

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.

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: ```cpp int a[10000005],b[10000005]; unsigned seed; unsigned rnd(unsigned x){ x^=x17; x^=xn>>seed; for(int i=1;i

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

**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