#P18267. Gathering Mushrooms

Gathering Mushrooms

Gathering Mushrooms

题目描述

BaoBao 在森林里采蘑菇。森林有 nn 个地点,编号为 1,…,n1,\ldots,n。地点 ii 有无限多个类型为 tit_i 的蘑菇,还有一块指向地点 aia_i 的木牌,允许 ai=ia_i=i。

雾很浓,为了安全,BaoBao 完全按照木牌移动。从地点 ss 出发时,他的篮子为空。每次到达地点 cc,包括最开始所在的 ss,也包括重复到达已经去过的地点,他都会先采一个类型为 tct_c 的蘑菇,再移动到 aca_c。

给定正整数 kk。对于每个起点 ss,设 vsv_s 为篮子中数量最先达到至少 kk 个的蘑菇类型。请计算所有起点的答案的加权和。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含三行:

  • 第一行两个整数 n,kn,k。
  • 第二行 nn 个整数 t1,…,tnt_1,\ldots,t_n。
  • 第三行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

每个测试用例输出一行一个整数:

∑i=1ni vi.\sum_{i=1}^{n}i\,v_i.

不需要逐个输出 viv_i。答案不取模,请使用 64 位整数保存。

数据范围

  • 1≤T≤1041\le T\le10^4。
  • 1≤n≤2×1051\le n\le2\times10^5,1≤k≤1091\le k\le10^9。
  • 1≤ti≤n1\le t_i\le n,1≤ai≤n1\le a_i\le n。
  • 每个输入文件中所有测试用例的 nn 之和不超过 2×1052\times10^5。

样例

3
5 3
2 2 1 3 3
2 5 1 2 4
5 4
2 2 1 3 3
2 5 1 2 4
3 10
1 2 3
1 3 2
41
45
14

样例说明

第一个测试用例中,(v1,v2,v3,v4,v5)=(2,3,2,3,3)(v_1,v_2,v_3,v_4,v_5)=(2,3,2,3,3),因此输出 1×2+2×3+3×2+4×3+5×3=411\times2+2\times3+3\times2+4\times3+5\times3=41。

例如从 s=3s=3 出发,依次采到的类型是 1,2,2,3,3,2,…1,2,2,3,3,2,\ldots,类型 22 最先达到三次。