P4437 [HNOI/AHOI2018] 排列

给定 $n$ 个整数 $a_1, a_2, \dots, a_n, 0 \le a_i \le n$，以及 $n$ 个整数 $w_1, w_2, \dots, w_n$。称 $a_1, a_2, \dots, a_n$的 一个排列 $a_{p[1]}, a_{p[2]}, \dots, a_{p[n]}$为 $a_1, a_2, \dots, a_n$的一个合法排列，当且仅当该排列满足：对于任意 的 $k$ 和任意的 $j$，如果 $j \le k$，那么 $a_{p[j]}$不等于 $p[k]$。（换句话说就是：对于任意的 $k$ 和任意的 $j$，如果 $p[k]$等于 $a_{p[j]}$，那么 $k

无

无

【样例解释 1】 对于 $a_1=0,a_2=1,a_3=1$，其排列有 $a_1=0,a_2=1,a_3=1$，是合法排列，排列的权值是 $1*5+2*7+3*3=28$； $a_2=1,a_1=0,a_3=$1，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_1=0,a_3=1,a_2=$1，是合法排列，排列的权值是 $1*5+2*3+3*7=32$； $a_3=1,a_1=0,a_2=1$，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_2=1,a_3=1,a_1=0$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_3=1,a_2=1,a_1=0$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$。 因此该题输出最大权值 $32$。 【样例解释 2】 对于 $a_1=2,a_2=3,a_3=1$，其排列有： $a_1=2,a_2=3,a_3=1$，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_2=3,a_1=2,a_3=1$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_1=2,a_3=1,a_2=3$ ，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_3=1,a_1=2,a_2=3$ ，是非法排列，因为 $a_{p[2]}$等于 $p[3]$； $a_2=3,a_3=1,a_1=2$ ，是非法排列，因为 $a_{p[2]}$等于 $p[3]$； $a_3=1,a_2=3,a_1=2$ ，是非法排列，因为 $a_{p[1]}$等于 $p[3]$ 因此该题没有合法排列。 【数据范围】 对于前 $20\%$ 的数据，$1 \le n \le 10$。 对于前 $40\%$ 的数据，$1 \le n \le 15$。 对于前 $60\%$ 的数据，$1 \le n \le 1000$。 对于前 $80\%$ 的数据，$1 \le n \le 10^5$。 对于 $100\%$ 的数据，$1 \le n \le 5\times10^5$，$0 \le a_i \le n$，$1 \le w_i \le 10^9 $，所有$w_i$的和不超过 $1.5×10^{13}$。