Gathering Mushrooms
题目描述
BaoBao 在森林里采蘑菇。森林有 n 个地点,编号为 1,…,n。地点 i 有无限多个类型为 ti 的蘑菇,还有一块指向地点 ai 的木牌,允许 ai=i。
雾很浓,为了安全,BaoBao 完全按照木牌移动。从地点 s 出发时,他的篮子为空。每次到达地点 c,包括最开始所在的 s,也包括重复到达已经去过的地点,他都会先采一个类型为 tc 的蘑菇,再移动到 ac。
给定正整数 k。对于每个起点 s,设 vs 为篮子中数量最先达到至少 k 个的蘑菇类型。请计算所有起点的答案的加权和。
输入格式
第一行一个整数 T,表示测试用例数。
每个测试用例包含三行:
- 第一行两个整数 n,k。
- 第二行 n 个整数 t1,…,tn。
- 第三行 n 个整数 a1,…,an。
输出格式
每个测试用例输出一行一个整数:
i=1∑nivi.
不需要逐个输出 vi。答案不取模,请使用 64 位整数保存。
数据范围
- 1≤T≤104。
- 1≤n≤2×105,1≤k≤109。
- 1≤ti≤n,1≤ai≤n。
- 每个输入文件中所有测试用例的 n 之和不超过 2×105。
样例
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),因此输出 1×2+2×3+3×2+4×3+5×3=41。
例如从 s=3 出发,依次采到的类型是 1,2,2,3,3,2,…,类型 2 最先达到三次。