当前没有测试数据。

题目类型说明

这是一道提交函数题 / 交互库调用题。你需要实现题目要求的函数，不需要编写 main 函数，也不能从标准输入读取或向标准输出写入。

你需要实现两个函数：

void learn(int n);
int ask_contestant(int a, int b);

评测程序会提供函数：

int ask_judge(int a, int b);

其中，ask_judge 只能在 learn 阶段调用；在回答阶段，ask_contestant 不能调用 ask_judge。

---

题目描述

给定一棵隐藏树，共有 N 个顶点，但你并不知道它的边集。树上的每条边都有一个权值，所有边权恰好是 1,2,...,N-1 的一个排列。

你可以询问两点 a、b 之间简单路径上最大边权是多少。

整个过程分为两个阶段：

第一阶段，你可以最多发出 8 × 10^6 次询问，用于“学习”这棵树的信息。
第二阶段，当你声明学习结束后，评测程序会给你 Q 个同类询问，你必须回答这些询问的结果；在这一阶段你不能再向评测程序提问。

你的任务是设计学习策略，并在回答阶段正确返回路径最大边权。

---

实现细节

你需要实现如下两个函数：

1. learn

void learn(int n);

• 参数 n 表示顶点个数 N。
• 在该函数中，你可以调用评测程序提供的：

int ask_judge(int a, int b);

该函数返回顶点 a 到顶点 b 的路径上的最大边权。

2. ask_contestant

int ask_contestant(int a, int b);

• 该函数需要返回顶点 a 到顶点 b 的路径上的最大边权。
• 在该函数中，不能调用 ask_judge。

你的程序文件应命名为 maxpath.cpp，并且：

• 不得包含 main 函数；
• 可以包含全局变量和辅助函数；
• 不得读写标准输入输出；
• 必须包含头文件：

#include "maxpath.h"

---

本地测试

题目提供本地 grader：Lgrader.cpp。

本地测试输入格式如下：

第一行输入一个整数 N。
接下来 N-1 行中，第 i 行给出从顶点 i 到顶点 i+1, i+2, ..., N 的路径最大边权。
随后输入一个整数 Q，再输入 Q 组询问 (a, b)。

---

数据范围

• 1 <= N <= 2 × 10^5
• 1 <= Q <= 4 × 10^6

最多可调用 ask_judge 的次数为：

• 8 × 10^6

---

子任务

子任务	分值	N 上限	Q 上限	额外限制
1	4	2 × 10^3	2 × 10^5	无
2	9	2 × 10^5		顶点 i 与 i+1 相连，对所有 1 <= i <= N-1 成立
3	17			存在一个顶点与所有其他顶点相连
4	21			顶点 p[i] 与 p[i+1] 相连，其中 p 是随机生成的排列，边权也随机生成
5	25			顶点 p[i] 与 p[i+1] 相连，其中 p 是一个排列
6	18		2 × 10^6	无
7	6		4 × 10^6

只有通过该子任务中的所有测试，才能获得该子任务的分数。

---

样例（本地 grader）

输入

3
1 2
2
3
1 2
1 3
2 3

输出

Correct

样例解释

这是本地 grader 的测试样例。其含义为：

• N = 3
• 接下来两行给出隐藏树对应的“路径最大边权信息”
• Q = 3
• 三个询问分别为 (1,2)、(1,3)、(2,3)

若你的程序对所有询问回答正确，本地 grader 会输出 Correct。

---

说明

这是一道典型的“两阶段交互 / 库调用”题：

• 第一阶段通过 learn 调用 ask_judge 学习隐藏树；
• 第二阶段通过 ask_contestant 回答询问。

请特别注意：

• 回答阶段不能继续调用 ask_judge；
• 题目时间压力较大，需要重视常数优化。