← 返回题目列表

Codeforces · 1519/C

C. 贝尔兰地区

中文机器翻译题面 查看原题

Polycarp 是 Berland ICPC 区域活动的组织者。伯兰有 $$$n$$$ 大学,编号从 $$$1$$$ 到 $$$n$$$。波利卡普认识该地区所有有竞争力的程序员。有 $$$n$$$ 个学生:第 $$$i$$$ 个学生就读于大学 $$$u_i$$$,并且具有编程技能 $$$s_i$$$。

坡旅甲现在必须决定规则。特别是团队成员的数量。

Polycarp 知道,如果他选择团队规模为某个整数 $$$k$$$,则每所大学都会将其 $$$k$$$ 最强(具有最高编程技能 $$$s$$$)的学生发送到第一团队,接下来的 $$$k$$$ 最强学生发送到第二团队,依此类推。如果剩下的学生少于$$$k$$$,则无法组建团队。请注意,可能有些大学派出零支球队。

该地区的实力是所有在场队伍成员技能的总和。如果没有队伍在场,则实力为$$$0$$$。

帮助 Polycarp 找出 $$$k$$$ 从 $$$1$$$ 到 $$$n$$$ 的每个选择的区域强度。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 大学数量和学生数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$u_1, u_2, \dots, u_n$$$ ($$$1 \le u_i \le n$$$) - 第 $$$i$$$ 学生就读的大学。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — 第 $$$i$$$ 个学生的编程技能。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数:该地区的实力 - 当前团队成员的总技能 - 对于每个团队规模 $$$k$$$ 的选择。

示例

输入 #1

4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083

输出 #1

29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083

注意

在第一个测试用例中,每个 $$$k$$$ 来自每所大学的团队是:

- $$$k=1$$$:大学$$$1$$$:$$$[6]、[5]、[5]、[3]$$$; 大学$$$2$$$: $$$[8], [1], [1]$$$;
- $$$k=2$$$:大学$$$1$$$:$$$[6, 5],[5, 3]$$$; 大学 $$$2$$$: $$$[8, 1]$$$;
- $$$k=3$$$: 大学 $$$1$$$: $$$[6, 5, 5]$$$; 大学$$$2$$$: $$$[8, 1, 1]$$$;
- $$$k=4$$$:大学$$$1$$$:$$$[6,5,5,3]$$$;