「EZEC-6」造树
题目背景
> 成体系的结论会产出“低猜想水平”的机械推导,但更多的题目中需要“高猜想水平”的灵感。
——command_block 《考前小贴士》
[](https://cdn.luogu.com.cn/upload/image_hosting/1m9hce9x.png)无脑选手出思维题。
题目描述
你要帮 djy 造一棵树,满足以下条件:
- 由 $n$ 个点组成。
- $i$ 号点的度数为 $a_i$。
定义一条边 $(i,j)$ 的价值为 $b_i\times b_j$,你要在满足上述两个条件下,使所有边的价值和最大。
保证存在这样的树。
输入输出格式
输入格式
第一行一个整数 $type$,表示数据生成方式。
若 $type=0$:
第二行一个整数 $n$。
第三行 $n$ 个整数,第 $i$ 个数表示 $a_i$。
第四行 $n$ 个整数,第 $i$ 个数表示 $b_i$。
若 $type=1$:
给出一个数据生成器模板:
```cpp
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>>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)]++;
}
```
第二行一个整数 $n$。
之后调用 `init_data()`。
第三行一个整数 $seed$。
输出格式
一行一个整数 $ans$,表示最大的价值和。
输入输出样例
输入样例 #1
0
5
1 2 3 1 1
5 3 1 7 9
输出样例 #1
42
输入样例 #2
1
10
114514
输出样例 #2
249899101316
说明
**本题采用捆绑测试。**
- Subtask0 (10 pts):$n\le 6$,$type=0$;
- Subtask1 (20 pts):$n\le 10^3$,$type=0$;
- Subtask2 (10 pts):$n\le5\times10^5$,$b_i\le2$,$type=0$;
- Subtask3 (20 pts):$n\le10^5$,$type=0$;
- Subtask4 (20 pts):$n\le5\times10^5$,$type=0$;
- Subtask5 (20 pts):$type=1$。
对于 $100\%$ 的数据,$2\le n\le10^7$,$1\le a_i\le n$,$1\le b_i\le5\times10^5$,$type\in\{0,1\}$,$0\le seed<2^{31}$。