题目描述

这是一道交互题。保证在询问合法的情况下，交互库占用运行时间不超过 500ms，空间不超过 128MB。因此你的程序运行时间不应超过 1500ms，空间不超过 896MB。

给你一棵 $N$ 个点的树，节点编号为 $0\sim N-1$，点 $i$ 有一个未知的整数点权 $a_i$，保证 $0\le a_i<32$。每次你可以给出整数 $x,d,v$，向交互库询问：在树上距离 $x$ 恰为 $d$ 的点中，有多少个点 $y$ 满足 $a_y\le v$。你需要在不超过 $M$ 次询问内求出每个点的点权。并且询问的 $d$ 不小于给定的限制 $L$。 保证不存在一个点的度数为 $N-1$。定义树上两点的距离为两个点最短路径经过的边数。

输入格式

【实现细节】

选手不需要，也不应该实现 main 函数。 选手应确保提交的程序包含头文件 tree.h，可在程序开头加入以下代码实现：

#include "tree.h"

选手需要实现以下函数:

std::vector<int> tree(int N, std::vector<std::pair<int,int> > E,int M,int L);

• $N$ 表示树的节点个数。
• $E$ 表示树的边集，大小为 $N-1$，其中的元素 $(u,v)$ 表示存在一条连接 $u$ 和 $v$ 的边;
• $M$ 表示询问次数限制。
• $L$ 表示询问的 $d$ 的限制。
• 该函数需要返回长为 $N$ 的数组 $ret$，编号 $0\sim N-1$，其中 $ret_i=a_i$。
• 对于每个测试点，该函数会被交互库调用恰好 $1$ 次。

选手可以通过调用以下函数向交互库发送一次询问:

int ask(int x, int d, int v);

• 你需要确保 $0\le x<N$，$L\le d\le N$，$0\le v<32$。
• 该函数会返回在树上距离 $x$ 恰为 $d$ 的点 $y$ 中，满足 $a_y\le v$ 的点的个数。

【测试程序方式】

下发文件中的 template_tree.cpp 是一份示例代码，grader.cpp 是提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库的实现。

选手可以在本题目录下使用如下命令编译得到可执行程序:

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

对于编译得到的可执行程序:

• 可执行文件将从标准输入读入以下格式的数据:
  • 输入的第一行包含三个非负整数 $N,M,L$，表示树的节点个数和询问限制。
  • 接下来一行输入一个非负整数 $R_1$，表示树的生成方式，如果 $R_1=0$，则接下来 $N-1$ 行，每行读入两个数 $u,v$，表示树上的边。否则将会以 $R_1$ 为 随机种子，对 $1\le i<N$ 随机生成 $0\le fa_i<i$，树上的每条边为 $(fa_i,i)$。
  • 接下来一行输入一个非负整数 $R_2$，表示点权的生成方式，如果 $R_2=0$，则接下来一行读入 $N$ 个数 ，第 $i$ 个数为 $a_i$，表示 $i$ 的点权。否则将会以 $R_2$ 为 随机种子，对 $0\le i<N$ 随机生成 $0\le a_i<32$。

输出格式

无

说明/提示

【数据范围】

本题共有 $3$ 个子任务。所有数据均满足 $N=50000$。

其中，对于子任务 $2$ 和子任务 $3$，有更特别的评分方式，假设你实际询问次数为 $Q$，那么你可以获得的分数占该子任务满分的百分比为：