시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 256 MB | 22 | 8 | 4 | 22.222% |
Prof. Elephant has a sequence $a_1, a_2, \ldots, a_n$. He has used the sequence to generate an undirected graph $G$ with $n$ vertices labeled by $1, 2, \ldots, n$.
For each even-length contiguous subsequence $a_l, a_{l + 1}, \ldots, a_{l + 2 k - 1}$, if $a_{l + i - 1} = a_{l + k + i - 1}$ always holds for $i = 1, 2, \ldots, k$, Prof. Elephant would add $k$ edges to $G$, where the endpoints of the $i$-th edge are vertices labeled by $(l + i - 1)$ and $(l + k + i - 1)$, and its weight is $w_k$.
Prof. Elephant would like to know the total weight of the minimum spanning forest of $G$.
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($2 \leq n \leq 3 \times 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).
The third line contains $\lfloor\frac{n}{2}\rfloor$ integers $w_1, w_2, \ldots, w_{\lfloor\frac{n}{2}\rfloor}$ ($1 \leq w_i \leq 10^9$).
It is guaranteed that the sum of $n$ in all test cases will not exceed $3 \times 10^5$.
For each test case, output an integer denoting the total weight of the minimum spanning forest of $G$.
1 8 2 2 5 6 2 5 6 2 5 1 4 4
21