AT_abc019_4 [ABC019D] 高橋くんと木の直径

高桥君正沉迷于求树的直径。树是一种由顶点和连接这些顶点的边组成的结构（“图”中的一种），如果顶点数为 $N$，则边的数量为 $N-1$，并且任意两个顶点都通过边直接或间接连通。 在本题中，每条边都有一个整数权重。定义两个顶点之间的距离为连接这两个顶点的路径上所有边权的和。 树的直径指的是所有顶点对中距离最大的那一对顶点之间的距离。 比如，考虑如下的树。边上的数字表示该边的权重。  在这个例子中，顶点 $1$ 和 $2$ 之间的距离为 $1$，顶点 $2$ 和 $4$ 之间的距离为 $1+2=3$。顶点 $3$ 和 $5$ 之间的距离为 $3+4=7$，顶点 $4$ 和 $5$ 之间的距离也是 $2+1+4=7$。这个树中最大的距离是 $7$，因此树的直径为 $7$。 高桥君对通过顶点数和两点间距离信息来求树的直径产生了兴趣。本题中，你将首先获得树的顶点数 $N$，然后可以多次询问任意两点之间的距离，最终要求你求出树的直径。 不过，询问两点间距离的次数有限制。 请在限定的询问次数内，编写程序求出树的直径。

首先，树的顶点数 $N$ 通过标准输入给出。 > $N$ 接下来，你的程序可以多次向评测程序发起询问。询问的格式如下： > ? $a$ $b$ 通过这个询问，你可以获得 $a$ 和 $b$ 之间的距离，评测程序会将结果通过标准输入返回一行。要求 $1 \leq a, b \leq N$ 且 $a \neq b$。 在进行若干次询问后，你需要输出树的直径。假设树的直径为 $diameter$，则输出格式如下： > ! $diameter$ 输出树的直径后，程序必须立即结束。如果没有立即结束，评测结果将不确定。 如果输出格式不符合上述要求，评测结果也将不确定。 本题每个测试点都有限定的最大询问次数。如果你的询问次数超过上限，将被判为错误。 判定正误以你输出的树的直径为准。即使你的询问不能唯一确定直径，只要输出的直径是正确的，也会被判为正确。 - - - - - - 以下是一些语言中，如何询问顶点 $1$ 和 $2$ 之间距离并读取结果 $dist$ 的示例。 注意，输出后需要刷新缓冲区（flush），否则可能会TLE。 C ``` printf("? %d %d\n", 1, 2); fflush(stdout); scanf("%d", &dist); ``` C++ ``` cout

无特殊输出格式说明，见题目描述。

### 限制 - $2 \leq N \leq 50$ - $1 \leq$（每条边的权重）$\leq 10^6$ ### 部分分 本题设置了部分分。 - 有 $20$ 分的测试点，询问次数上限为 $1300$ 次。 - 另有 $80$ 分的测试点，询问次数上限为 $100$ 次。 ### 输入输出样例 当树的结构如下图所示时：  可能的输入输出如下： 程序输入 程序输出 5 ? 1 2 5 ? 2 4 1 ? 4 5 2 ? 2 3 9 ? 1 5 8 ! 14 这只是输入输出的一个例子，未必是有意义的询问。 由 ChatGPT 4.1 翻译