#P15992. [2024国家队集训中科院站]星际矿业

[2024国家队集训中科院站]星际矿业

题目描述

Alice 和 Bob 正在玩一款星际开发游戏。游戏中有 nn 个星球,编号为 11 到 nn。星球 uu 上的矿物储量为 wuw_u。

为了在不同星球之间移动,星际公司建造了 n−1n-1 个星门,规则如下:

  • 对每个星球 u∈{2,3,…,n}u\in\{2,3,\dots,n\},星球 uu 上恰好有一个星门;
  • 给定 p2,p3,…,pnp_2,p_3,\dots,p_n,星球 uu 上的星门通向星球 pup_u;
  • 星门是单向的,不能反向通过;
  • 从任意星球出发,都可以沿星门到达星球 11。星球 11 上有星际市场。

Bob 有 kk 艘采矿船。他可以把这 kk 艘采矿船部署到 kk 个不同的星球上。每艘采矿船可以沿星门移动,并收集其路径上经过星球的全部矿物储量。一个星球可以被多艘采矿船经过,但每个星球上的矿物最多只能被收集一次。最终,采矿船会到达星球 11,并在那里出售收集到的矿物。

然而,在 Bob 开始采矿前,触发了一次星门维护事件。星际公司决定更新星门布局:拆除 tt 个星门,并重新建造 tt 个星门,使得更新后的星门结构仍满足上述规则。由于游戏机制,tt 可以是 [0,n−1][0,n-1] 内的任意整数,也就是说,星门可以完全不更新。

经过一番外交点数交易后,拆除星门的任务被外包给 Alice,重建星门的任务被外包给 Bob。重建完成后,Bob 再部署采矿船进行采矿。

Bob 希望最大化自己收集到的矿物总量;Alice 希望最小化 Bob 最终能收集到的矿物总量。在此基础上,Alice 还希望拆除尽可能多的星门。

假设双方都采取最优策略,求:

  1. Bob 最终能收集到的矿物总量;
  2. 在保证该矿物总量最小的前提下,Alice 最多能拆除多少个星门。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 TT,表示测试数据组数。

对于每组测试数据:

第一行包含两个正整数 n,kn,k。

第二行包含 nn 个正整数 w1,w2,…,wnw_1,w_2,\dots,w_n,表示每个星球上的矿物储量。

第三行包含 n−1n-1 个正整数 p2,p3,…,pnp_2,p_3,\dots,p_n,表示初始状态下星球 uu 上的星门通向星球 pup_u。

输出格式

对于每组测试数据,输出一行两个非负整数,分别表示:

  • Bob 最终收集到的矿物总量;
  • 在使 Bob 收集总量最小的前提下,Alice 最多能拆除的星门数量。

样例

样例输入

3
3 1
1 1 1
1 1
7 2
5 8 8 5 8 2 3
1 2 3 4 1 4
16 4
2 7 9 7 9 5 10 10 2 10 5 2 7 6 9 4
1 1 3 3 1 6 5 8 3 10 2 7 8 9 3

样例输出

2 0
37 2
87 4

样例解释

对于第一组测试数据,如果 Alice 拆除星球 22 上的星门,那么 Bob 可以将其重建为 p2=3p_2=3,于是他只需要把唯一一艘采矿船放在星球 22,就能收集三个星球上的全部 33 单位矿物。拆除星球 33 上的星门时情况类似。

因此,Alice 最优选择是不拆除任何星门,此时 Bob 最多只能收集到 22 单位矿物。

对于第二组测试数据,Alice 的一种可行最优策略是拆除星球 22 和星球 33 上的星门。

数据范围

令 ∑n\sum n 表示单个测试文件中所有测试数据的 nn 之和。保证:

  • 1≤T≤1041\le T\le 10^4;
  • 1≤k≤n≤2×1051\le k\le n\le 2\times 10^5;
  • 1≤∑n≤5×1051\le \sum n\le 5\times 10^5;
  • 1≤wu≤1091\le w_u\le 10^9;
  • 对所有 2≤u≤n2\le u\le n,有 1≤pu≤u−11\le p_u\le u-1。

子任务

子任务编号 n≤n\le ∑n≤\sum n\le 特殊性质 分值
1 55 2525 无 5
2 2020 100100 13
3 25002500 60006000 A、B 4
4 A
5 B
6 无 10
7 2×1052\times 10^5 5×1055\times 10^5 A、B 7
8 A
9 B
10 无 39

特殊性质:

  • A:k=1k=1;
  • B:对所有 2≤u≤n2\le u\le n,都有 pu=1p_u=1 或 pu=u−1p_u=u-1。