P1059新水濯旧隍（moat）

本题为交互题。

【题目背景】

龙华于旸，红旗漫卷，新水濯旧隍。

【题目描述】

前朝遗老的王宫里，有 $n$ 个宫室，其中有一个宫室是明光殿，记为 $1$ 号宫室，这 $n$ 个宫室由 $n-1$ 条宫内道路连通，也就是说，任意两个宫室 $u,v$ 都能通过若干条宫内道路互相到达。第 $i$ 个宫室中收藏着价值 $w_i$ 的宝藏。每个 $w_i$ 都是正整数。

旧王朝被推翻后，清洗者和斥候来到了明光殿，决定探测整个王宫。前朝留下的宫图记录了所有宫内道路，却没有记载任何一处藏宝量。因此，在行动开始前，王宫的结构是已知的，而每个 $w_i$ 都是未知的。

以明光殿为根，宫室 $u$ 的深度定义为从明光殿前往宫室 $u$ 时经过的宫室数量。保证每个宫室至多与两个深度比它大 $1$ 的宫室直接相连。令 $h$ 表示所有宫室深度的最大值。

行动共进行 $b$ 轮。每轮行动依次分为探查阶段与清洗阶段。

对于一个宫室 $u$，将宫室 $u$ 与所有从明光殿前往时必须经过宫室 $u$ 的宫室共同组成的区域称为宫室 $u$ 的辖域。在探查阶段，你可以让斥候调查任意一个宫室 $u$，斥候会报告宫室 $u$ 的辖域中当前剩余的藏宝量之和。你可以根据此前得到的所有报告决定下一次调查的位置，也可以随时结束本轮的探查阶段。

随后进入本轮的清洗阶段。你必须让清洗者选择一个此前没有清洗过的宫室 $u$。清洗者会取得宫室 $u$ 中的全部财宝，并将这个宫室的藏宝量清零。此后，本轮行动结束，下一轮调查所得的藏宝量之和也会随之改变。

而你作为领导者，需要根据斥候不断送回的消息，为清洗者依次确定 $b$ 个互不相同的目标，使得最终获取的藏宝量尽可能多。视你获取的藏宝量多少，你将会获得不同的评价。

【实现细节】

选手不需要，也不应实现 main 函数。

选手需要确保提交的程序包含头文件 moat.h，即在程序开头加入以下代码：

1#include "moat.h"

选手需要在提交的程序源文件 moat.cpp 中实现以下两个函数：

1void Init(int c, int T);

• $c,T$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

1void Play(int c, int n, int b, std::vector<int> parent);

• $c,n,b$ 分别表示测试点编号、宫室数量与行动轮数。
• parent 的长度为 $n+1$。其中 parent[1] 等于 $0$，对于 $2\leq u\leq n$，parent[u] 表示从宫室 $u$ 前往明光殿时经过的第一个宫室。
• 选手可以由 parent 得知完整的王宫结构。每个宫室的藏宝量不会传入该函数。
• 对于每组测试数据，该函数会被交互库调用恰好一次。

在 Play 函数中，选手可以调用下列函数。

1long long Scout(int u);

• 该函数表示让斥候调查宫室 $u$，其中 $1\leq u\leq n$。
• 该函数返回宫室 $u$ 的辖域中当前剩余的藏宝量之和。
• 该函数只能在一轮行动的探查阶段调用。
• 设王宫的高度为 $h$。选手需要确保交互库每次调用 Play 时，调用该函数的次数不超过 $2bh+20$。

1long long Clean(int u);

• 该函数结束当前一轮的探查阶段，并让清洗者在清洗阶段清洗宫室 $u$，其中 $1\leq u\leq n$。
• 宫室 $u$ 不能在此前的清洗阶段中被选择过。
• 该函数返回本次取得的藏宝量。调用结束后，宫室 $u$ 的藏宝量变为 $0$，并立即开始下一轮的探查阶段。
• 每组测试数据中，该函数必须恰好调用 $b$ 次。第 $b$ 次调用结束后，Play 函数应当结束运行。

交互库运行所需的时间与空间均计入本题的时间与空间限制。

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行文件：

1g++ grader.cpp moat.cpp -o moat -O2 -std=c++14 -static

对于编译得到的可执行文件 moat：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。
  • 接下来对于每组测试数据，第一行包含两个正整数 $n,b$。
  • 第二行包含 $n$ 个正整数 $w_1,w_2,\cdots,w_n$。
  • 接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示宫室 $u,v$ 之间有一条宫内道路。

• 若所有交互均合法，可执行文件将输出以下格式的数据至标准输出：

  • 输出的第一行为 Finished!。
  • 接下来 $T$ 行中，第 $i$ 行形如 Case i: treasure = s, score ratio = p%，其中 $s$ 表示第 $i$ 组测试数据中取得的藏宝量，$p$ 表示该组测试数据的得分百分比。
  • 输出的最后一行为 Score ratio: p%，其中 $p$ 表示整个测试点的得分百分比。

• 若发生非法调用，可执行文件会向标准错误流输出错误信息并终止程序。

【样例 1 输入】

10 127 234 5 2 6 3 7 141 251 362 472 583 693 7

【样例 1 输出】

1Finished!2Case 1: treasure = 13, score ratio = 100.000000%3Score ratio: 100.000000%

【说明/提示】

【样例 1 解释】

样例输出对应一种分别清洗宫室 $4$ 与宫室 $6$ 的策略。两次清洗依次取得 $6$ 与 $7$ 的藏宝量，因此最终共取得 $13$ 的藏宝量。

不同的合法策略可能产生不同的样例输出。

【样例 2】

见选手目录下的 $\textbf{\textit{moat/moat2.in}}$。

该组样例符合测试点 $1$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{moat/moat3.in}}$。

该组样例符合测试点 $2$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{moat/moat4.in}}$。

该组样例符合测试点 $3$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{moat/moat5.in}}$。

该组样例符合测试点 $4$ 的数据范围。

本题为成果评分交互题，附加样例只提供隐藏输入。测试程序的输出由选手程序采用的策略决定。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 4$，$2\leq n\leq 2\times 10^5$，$1\leq b\leq\min(40,n)$，$1\leq w_u\leq 10^9$，每个宫室至多与两个深度比它大 $1$ 的宫室直接相连，王宫的高度 $h\leq 30$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$。

特殊性质 A：所有宫内道路构成一条以明光殿为一端的链。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如试图直接读取各个宫室的藏宝量，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。
• 交互库不是适应性的。每次调用 Play 时，王宫结构与各个宫室最初的藏宝量已经确定。只有选手调用 Clean 时，相应宫室的藏宝量才会按照【题目描述】中的规则变为 $0$。
• 最终的评测交互库与本地测试交互库的实现不同。

对于一组交互合法的测试数据，记所有宫室最初的藏宝量之和为 $v$，选手程序最终获取的藏宝量为 $s$。该组测试数据的得分比例为

其中，$p$ 表示该组测试数据的得分比例。若 $p=1$，则该组测试数据取得对应的全部分值。若 $p<1$，则该组测试数据取得对应分值的 $p$ 倍。

若一个测试点包含 $T$ 组测试数据，记第 $i$ 组测试数据的得分比例为 $p_i$，则该测试点的得分比例 $\bar p$ 为

可以等价地认为，测试点的分值被平均分配给其中的 $T$ 组测试数据，再分别乘以对应的得分比例。若选手程序在任意一组测试数据中发生非法调用，则整个测试点得 $0$ 分。

记表中该测试点的分值为 $d$，则取整前的实际得分为 $d\bar p$。最终得分保留两位小数，并采用向下取整，也就是