题目描述

Tom 有一棵 $n$ 个顶点的带权树（连通、无环，每条边有一个正整数权值），顶点编号 $1 \sim n$。33DAI 看不到这棵树，他只能向 Tom 询问两个顶点之间的距离。

33DAI 想知道这棵树的直径：所有顶点对之间距离的最大值。请你帮他问出来，并且问的次数要尽量少。

本题是函数式交互题。你不需要写 main 函数，只要实现下面两个函数（在随题下发的 tree.h 里声明）。你的源文件里必须写上 #include "tree.h"，否则无法编译。

void init(int t, int n);
long long diameter();

• init(t, n)：每个测试点开始时调用一次。$t$ 是这个测试点里树的棵数，$n$ 是每棵树的顶点数（相同）。
• diameter()：返回当前这棵树的直径。每棵树的询问次数从 $0$ 开始计。

你可以调用下面这个函数向评测程序提问：

long long distance(int u, int v);

• 返回顶点 $u$ 与 $v$ 之间唯一路径上的边权之和，要求 $1 \le u, v \le n$ 且 $u \ne v$。

评分方式：记 $M$ 为"这个测试点里，某一棵树问得最多的次数"。

• 只要有任何一棵树答错，本测试点得 $0$ 分；
• $M \le 3n$ 得满分（两趟"最远点"只需要 $2(n-1)$ 次询问）；
• $3n < M < 20n$ 时分数从满分线性降到 $0$；$M \ge 20n$ 得 $0$ 分。

输入格式

本题没有传统意义上的输入文件：数据由评测程序（grader）读入，你只要实现上面两个函数。

随题下发的文件（见「附加文件」）：

• tree.h：接口声明；
• grader.cpp：示例评测程序，只用来在本地把你的程序跑起来；
• compile.sh：编译脚本。

本地编译命令（把你自己的代码保存为 foo.cc，与上面三个文件放在同一个目录）：

g++ -o foo foo.cc grader.cpp -O2 -std=c++14

示例 grader 的本地输入格式是：第一行两个整数 $t, n$；之后每棵树两行 —— 先是 $n-1$ 个整数表示顶点 $2 \sim n$ 的父亲（保证父亲编号小于自己），再是 $n-1$ 个整数表示对应边的权值。

注意：示例 grader 只用于本地自测，它的数据格式、数据范围与判分方式都和正式评测不同； 正式评测使用另一份 grader，请以题面写明的接口与规则为准。

输出格式

不需要输出任何东西：diameter() 的返回值就是答案，由评测程序收集。

样例

某个测试点里 $t = 1$、$n = 4$，树是 $1 - 3$（权值 $2$）、$2 - 3$（权值 $5$）、$3 - 4$（权值 $1$）。

一次合法的交互过程：

你的程序                  评测程序
distance(1, 2)  ->        7        （1-3-2，2 + 5）
distance(1, 3)  ->        2
distance(1, 4)  ->        3
distance(2, 4)  ->        6        （2-3-4，5 + 1）
diameter() 返回 7                 （最远的顶点对是 1 和 2，距离 7）

这次一共问了 $4$ 次，$n = 4$、门槛是 $3n = 12$，所以得满分。

提示

• 本题是函数式交互题：tree.h、grader.cpp、compile.sh 随题下发，你只提交实现 init / diameter 的源文件。
• 别想着把整棵树"问出来"：那需要约 $n^2/2$ 次询问，远超门槛。
• 树有一个经典性质可以把询问次数降到 $O(n)$：从任意点出发，距离它最远的点一定是某条直径的端点。
• 同一组数据里每棵树的询问次数单独统计，最后取最大的那个。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 20$；
• $2 \le n \le 500$；
• 每条边的权值在 $[1, 10^4]$ 内，树保证连通且无环。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点计分。