P14193 [ICPC 2024 Hangzhou R] Gathering Mushrooms

BaoBao 在森林里采蘑菇。森林里共有 $n$ 个位置，第 $i$ 个位置长着无限多的 $t_i$ 型蘑菇。每个位置都有一个木牌，第 $i$ 个位置的木牌指向位置 $a_i$（可能有 $a_i = i$）。 由于森林里雾气很大，BaoBao 决定按照木牌的指示在各个位置间移动以保证安全。BaoBao 从位置 $s$ 出发，手里拿着一个空篮子，每次进入位置 $c$（包括出发时 $c = s$，无论是否之前到过位置 $c$），都会采摘一个 $t_c$ 型的蘑菇放进篮子里，然后沿着指示牌走到 $a_c$ 位置。 给定整数 $k$，对于每个 $1 \le s \le n$，请你确定第一个在篮子里出现次数至少为 $k$ 的蘑菇类型。

有多组测试数据。第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。每组测试数据中： 第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$），分别表示位置数和要求的出现次数。 第二行包含 $n$ 个整数 $t_1, t_2, \cdots, t_n$（$1 \le t_i \le n$），表示第 $i$ 个位置长的蘑菇类型。 第三行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$），表示第 $i$ 个位置的木牌所指向的位置编号。 保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

为减少输出数据量，对于每组测试数据，输出一行一个整数，表示 $\sum\limits_{i = 1}^{n} (i \times v_i)$，其中 $v_i$ 表示 $s = i$ 时的答案。

对于第一个样例，$v_1 = 2$，$v_2 = 3$，$v_3 = 2$，$v_4 = 3$，$v_5 = 3$，因此应输出 $1 \times 2 + 2 \times 3 + 3 \times 2 + 4 \times 3 + 5 \times 3 = 41$。以 $s = 3$ 为例，BaoBao 采蘑菇的顺序是 $\{1, 2, 2, 3, 3, 2, \cdots\}$，因此类型为 $2$ 的蘑菇最早在篮子里出现了不少于 $3$ 次。 由 ChatGPT 5 翻译