U365250 [The 2023 ICPC AROC II] I Impatient Patient

暂无数据，提交请到：

You accidentally sprained your ankle, and now you are facing a long recovery phase. Initially, you are at stage $0$, and your recovery progresses until you reach stage $n$. Each day, if you rest properly, you advance by exactly one stage. So it takes $n$ days for you to recover, that is, if you do not do anything improper. However, instead of resting, you have the option to challenge yourself, which also takes one day. If you are at stage $i$ and succeed, you will instantly recover. However, if you fail, you will regress to stage $a_i\space(0\le a_i \le i)$. The probability of success is $p_i$. Now, you are wondering what the expected time required for your recovery would be, assuming you adopt the best strategy.

The first line contains a positive integer $T$ ($1\le T\le 10^4$), denoting the number of test cases. For each test case: * The first line contains one integer $n$ ($1\le n\le 5\times 10^5$), denoting the number of stages of recovery. * The next line contains $n$ integers $a_0,a_1,\cdots,a_{n-1}$ ($0 \le a_i\le i$), denoting the stage you will go back to if you fail at stage $i$. * The next line contains $n$ integers $q_0,q_1,\cdots,q_{n-1}$ ($0 \le q_i\le 10^5$), where $p_i=q_i/10^5$ denotes the probability of success at stage $i$. It is guaranteed that $\sum n \le 5\times 10^5$.

For each test case, print one decimal number, denoting the expected time needed for you to recover if you take the best strategy. The answer will be considered correct if its absolute or relative error is less than $10^{-9}$.

| 代码长度限制 | 时间限制 | 内存限制 | | :-: | :-: | :-: | | 64 KB | 1000 ms | 512 MB |