P14193 [ICPC 2024 Hangzhou R] Gathering Mushrooms

BaoBao is picking mushrooms in a forest. There are $n$ locations in the forest, and in the $i$-th location there grows an infinite amount of mushrooms of type $t_i$. Each location also has a wooden sign. The sign of the $i$-th location points to location $a_i$ (it is possible that $a_i = i$). As it is very foggy in the forest, BaoBao decides to move between locations according to the signs just for safety. Starting from location $s$ with an empty basket, each time BaoBao walks into a location $c$ (including the starting location $c = s$, and regardless of whether he has visited location $c$ before), he will pick one mushroom of type $t_c$ into his basket and move to location $a_c$. Given an integer $k$, for each $1 \le s \le n$, determine the first type of mushroom that appears at least $k$ times in the basket.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le 10^9$) indicating the number of locations and the required times of appearance of mushrooms. The second line contains $n$ integers $t_1, t_2, \cdots, t_n$ ($1 \le t_i \le n$), where $t_i$ is the type of mushroom growing in location $i$. The third line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the location pointed to by the sign in location $i$. It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^5$.

To decrease the size of output, for each test case, output one line containing one integer indicating $\sum\limits_{i = 1}^n (i \times v_i)$, where $v_i$ is the answer for $s = i$.

For the first sample test case, $v_1 = 2$, $v_2 = 3$, $v_3 = 2$, $v_4 = 3$, $v_5 = 3$, so you should output $1 \times 2 + 2 \times 3 + 3 \times 2 + 4 \times 3 + 5 \times 3 = 41$. Consider $s = 3$, the types of mushrooms BaoBao picks in order are $\{1, 2, 2, 3, 3, 2, \cdots\}$, so mushrooms of type $2$ is the very first type which appears at least $3$ times in the basket.