UOJ Logo Universal Online Judge

UOJ

附件下载 统计

这是一道交互题,仅支持 C++ 语言提交。

小青鱼计划越过高高的龙门,成为大青龙。但是仅凭小青鱼的力量是越不过龙门的。所以它在被称作老龙宫的溶洞中探险,如果能游历幽深之处,就能获得神奇的云崖潮生之珠。

龙门水道的地下有复杂的溶洞,具体来说,溶洞可以被视为有 $n$ 个节点的树,点的编号为依次为 $1$ 到 $n$。

令 $\mathrm{dist}(u, v)$ 表示树上 $u$ 到 $v$ 的简单路径包含的边数,$f(l, r) = \max\limits_{l \le u \le v \le r} \mathrm{dist}(u, v)$。

小青鱼还不知道溶洞的具体结构。在探险之前,小青鱼打算用探测器对溶洞进行调查。只要在节点 $u,v$ 埋下探测器,就可以算出 $u,v$ 之间的距离 $\mathrm{dist}(u, v)$。

小青鱼需要知道这个溶洞是否具有足够的仙力,只有足够幽曲蜿蜒的地方才能诞生出强大的云崖潮生之珠。

具体地,小青鱼想求出 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$,即区间直径长度之和。这个值同时也是云崖潮生之珠的仙力估计值。

题目保证树的形态是预先给定的,不会根据你的操作而动态生成

一句话题意:每次可询问 $\mathrm{dist}(u, v)$,需要求出 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$。


实现细节

你需要引用头文件 #include "tree.h"。你可以调用以下函数与交互库进行交互:

int query(int u, int v);

  • 这个函数会返回 $u$ 到 $v$ 的距离。
  • 你需要保证 $1 \le u, v \le n$。

你不需要,也不应该实现主函数。在本题中,你只需要实现如下函数:

long long solve(int type, int n);

  • 其中 $\text{type}$ 表示数据类型,$n$ 表示树的点数,函数的返回值应为 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$。
  • 最终测试时,对于每个测试点,交互库会调用恰好 $T$ 次 solve 函数,并根据调用 solve 函数的返回值正误来评分。

在选手目录(题目附件)中,我们提供了 sample.cpp 供你参考,你可以在此基础上实现你的程序。


测试程序方式

本题目录下提供了 grader.cpp 文件(该文件使用了部分标准中不包含的函数,如有需要,可以使用 grader2.cpp)。最终测试的交互库与下发交互库有不同,因此你的实现不应依赖交互库实现。

你需要将你的程序 tree.cppgrader.cpptree.h 放置在同一目录下,并在该目录下使用如下编译命令得到可执行程序 tree(.exe)

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

可执行程序从标准输入读入以下格式的数据:

  • 第一行包含一个正整数 $T$,表示数据组数。

对于每组数据:

  • 第一行,共两个整数 $\text{type},n$。交互库保证可以处理 $2 \le n \le 10^5$ 的情况,对于 $n > 10^5$ 的情况不做正确运行保证。
  • 接下来 $n - 1$ 行,每行包含两个正整数 $u, v$,表示了树上一条边。你需要保证 $1 \le u, v \le n$ 且输入给出了合法的树的结构

在本地测试时,请务必保证你的输入格式符合要求,否则我们不保证交互库会正常运行

如果你的输入合法且没有运行错误,下发的交互库将会根据你的调用输出如下信息:

  • 如果某次 query 函数的调用违反了 $1 \le u, v \le n$ 的限制,输出错误信息:Wrong Answer 0!,并且交互库立即终止。
  • 如果 solve 函数的返回值正确,那么交互库会输出三个数,依次表示:solve 函数的返回值,$n$ 的值,query 函数的调用次数。

你的程序不应该操作标准输入输出,否则视为攻击交互库

样例一

见下发文件中的 ex_tree1.in/out

样例二

见下发文件中的 ex_tree2.in/out

样例三

见下发文件中的 ex_tree3.in/out

子任务

对于所有数据,$1 \leq T \leq 10^4, 1 \leq n \leq 10^5, \sum n \leq 3 \times 10^5, lim \geq 8 \times n$。

令 $k=\dfrac{lim}{n}$。

子任务编号 $\text{type}=$ $n=$ $T=$ $k=$ 分值
$1$ $1$ $10$ $10^4$ $10$ $10$
$2.1$ $2$ $10^3$ $50$ $50$ $12$
$2.2$ $8$ $28$
$3$ $3$ $10^5$ $3$ $8$ $15$
$4$ $4$ $16$ $15$
$5.1$ $5$ $100$ $8$
$5.2$ $8$ $12$

$\text{type}=3$ 的数据保证树为一条链。

$\text{type}=4$ 的数据保证 $f(1,n)\le 8$。


评分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。

在以上条件下,若 solve 函数的返回值正确,且在 $T$ 次 solve 过程中调用 query 函数的次数均不超过 $lim$,则相应测试点得满分,否则得 $0$ 分。

在实际测评中,对于子任务 2, 5 我们仅会测试一轮,并根据选手的询问次数给出相对应的分数。

保证在下发的交互库和最终评测的交互库中,query 函数的单次最坏复杂度为 $O(1)$,在题目限制下占用不超过 $1\texttt{s},256\texttt{MB}$。


提示

我们再次提醒:树的形态是预先给定的,不会根据你的操作而动态生成

你需要注意你的程序的时间开销和空间开销。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为,所得分数无效

时间限制:$5\texttt{s}$

空间限制:$1\texttt{GB}$