原题：洛谷 P17202「奶龙OI」Round 1 - 小猫的考试。以下保留原题面与评分规则。

本站提交方式：本题按 UOJ 提交答案题配置。请在本地生成答案，将答案保存为 test1.out 后上传（或将该文件放在 ZIP 根目录提交）。原题中的程序提交方式可通过在本地运行程序生成答案实现。仅有一个测试点，保留全部部分分档位。

题目背景

本题的另一个出题人是 @tanruiqing，本题是他的题目的数据生成器，但，这位出题人并非本题背景中的小猫或章鱼。

题目末尾给出了形式化题面。

章鱼和小猫正在比较谁是第一，小猫想要比较捉老鼠能力，章鱼想要比较游泳能力，谁也不让谁，于是他们决定比较 OI 能力。

他们想知道谁能解决更难的题，所以决定让小猫出一道题考章鱼。

如果章鱼解决了这道题，那么小猫就得让出所有的猫粮，否则章鱼就得承认小猫才是天下最聪明的。

题目描述

有一天，小猫出了一道题去考章鱼，题目如下：

题目

有一棵包含 $n$ 个结点的无根树，结点编号为 $1\sim n$。初始时每个结点 $i$ 有一个非负整数状态 $a_i$。

树每一轮会进行一次“更新”操作：每一轮所有结点的状态同时变为各自所有邻居在上一轮状态集合的最小未出现的非负整数（简称为 $mex$）。形式化地，设第 $t$ 次更新操作后，结点 $i$ 的状态为 $f_i(t)$，则：

$f_i(t+1)=\operatorname{mex}\{f_j(t)\mid j\text{ 是 }i\text{ 的邻居}\}$

特别地，$f_i(0)$ 表示 $i$ 点的初始状态。

其中 $mex(S)$ 表示不在集合 $S$ 中的最小非负整数。

令初始时刻为 $0$ 时刻，第 $i$ 次更新操作之后为 $i$ 时刻。

如果存在正整数 $l$ 满足 对于所有 $1\le u\le n$ 都有 $f_u(i)=f_u(i+l)$，则称这棵树在 $i$ 时刻进入循环。

可以证明该树一定会在有限轮后进入循环。现在，请你求出最小的非负整数 $x$，使得 $x$ 时刻树进入循环。

邻居的定义

在图论中，邻居（neighbor）是指与某个节点直接相连的节点。例如，如果节点 $v_i$ 与节点 $v_j$ 之间存在一条边，则 $v_j$ 是 $v_i$ 的邻居，反之亦然。在无向图中，邻居关系是对称的；而在有向图中，邻居关系则可能是单向的。

小猫原以为章鱼做不出来，所以没提前造数据，然而章鱼很快就秒掉了这道题，很快就要提交代码了，小猫赶紧找到了你，要求你尽快造一份数据，将章鱼的代码的时间卡得越大越好。

给定 $n$，要求你构造一棵 $n$ 个点的树，每个点的点权是一个值域 $[0,10^9]$ 的非负整数。

令 $(x,y)$ 为字典序最小的整数对 $(a,b)$，使得 $a$ 时刻的树与 $b$ 时刻的树完全一致，要求 $0\le a

若对于所有 $1\le i\le n$，均满足 $f_i(a)=f_i(b)$，我们称 $a,b$ 时刻的树一致。

你的得分关于 $x$ 单调不降，评分规则见【评分规则】。

特别注意，本题不关心你构造的树的 $y$ 值，你的程序的得分仅和 $x$ 有关。

输入格式

没有输入，$n$ 的值见【说明/提示】。

输出格式

第一行按照编号升序输出你构造的树的每个点的点权，相邻两个整数之间由单个空格隔开，共 $n$ 个整数。

第 $2\sim n$ 行输出你构造的树包含的每一条边，每一行输出两个正整数 $u,v$，表示这条边的两个端点。

你可以以任意顺序输出你构造的树包含的每一条边。

输出格式示意：

a[1] a[2] a[3] ... a[n]  
u[1] v[1]
u[2] v[2]
u[3] v[3]
...  
u[n-1] v[n-1]

本题支持提交答案，即，你可以选择提交一个程序作为你的答案的生成器，也可以直接提交将你本地构造出来的答案。

如果你选择直接提交本地构造出来的答案，则必须提交一个 zip 压缩包，内部放置答案的文本文件。

输入输出样例

无

说明/提示

在此题中，$n=200000$。

评分规则

本题仅有一个测试点。

如果你的程序无法编译，或者超时，或者给出的构造不是一颗树 ，或者你给出的点权不在 $[0,10^9]$ 以内，那么你的程序将会获得 $0$ 分。

随后将会按照以下规则评定分值：

令你构造的树进入循环的时刻为 $x$（含义等同于题目描述中的 $x$）。

本地测试说明

本题下发了 checker.cpp 以及 testlib.h，你可以使用它们检查你的答案的得分。

你可以运行 g++ checker.cpp -o checker -std=c++14 编译得到 checker，你需要确保编译 checker 的时候，checker.cpp 和 testlib.h 位于同一目录下。

使用 checker 的方法：

• 假设你构造的答案存放在 ans.txt。

• 命令行运行 checker ans.txt ans.txt ans.txt，注意这里没有笔误。

• 随后 checker 会告诉你，你的答案是否正确，以及你构造的答案的 $x$ 值，以及以此计算的得分比例。

形式化题面

点此展开形式化题面

题目描述

构造一棵包含 $n=200000$ 个结点的无根树。结点编号为 $1,2,\ldots ,n$，每个结点 $i$ 具有一个初始状态 $a_i$，其中 $a_i$ 是区间 $[0,10^9]$ 内的整数。

令 $f_i(t)$ 表示结点 $i$ 在时刻 $t$ 的状态。初始时刻为 $0$，即

$f_i(0)=a_i.$

对于每个非负整数 $t$，所有结点的状态同时更新，更新规则为

$f_i(t+1)=\operatorname{mex}(\{f_j(t)\mid j\text{ 与 }i\text{ 之间有边}\}),$

其中，$mex(S)$ 表示不属于集合 $S$ 的最小非负整数。

如果两个时刻 $a,b$ 满足

$f_i(a)=f_i(b)\quad(1\le i\le n),$

则称时刻 $a$ 与时刻 $b$ 的树状态完全一致。

在所有满足 $0\le a

$x$ 是满足存在 $y>x$，使时刻 $x,y$ 的树状态完全一致的最小非负整数；

在 $x$ 确定后，$y$ 是满足 $y>x$ 且时刻 $x,y$ 的树状态完全一致的最小整数。

该状态序列一定会在有限时间内出现重复状态。

需要构造树的边和所有结点的初始状态，使得 $x$ 尽可能大。评分仅取决于 $x$，与 $y$ 无关。

输入格式

本题没有输入。

固定有

$n=200000.$

输出格式

输出共 $n$ 行。

第一行输出 $n$ 个整数

$a_1,a_2,\ldots,a_n,$

表示各结点的初始状态。相邻两个整数之间以单个空格分隔。

接下来输出 $n-1$ 行。每行包含两个整数 $u,v$，表示树中存在一条连接结点 $u$ 和结点 $v$ 的无向边。

提交方式

本题支持以下两种提交方式：

• 提交一个无输入的答案生成程序，由程序输出上述构造；

• 直接提交本地生成的答案。此时必须提交一个 ZIP 压缩包，其中包含答案的文本文件。

本题只有一个测试点。

如果生成程序无法编译、运行超时，或者输出不符合格式、点权超出允许范围、输出的图不是一棵树，则得分为 $0$。

边可以按任意顺序输出。

输出必须满足：

• $0\le a_i\le 10^9$；

• $1\le u,v\le n$；

• 输出的 $n-1$ 条边必须构成一棵包含全部 $n$ 个结点的树。

输出格式如下：

a[1] a[2] a[3] ... a[n]
u[1] v[1]
u[2] v[2]
u[3] v[3]
...
u[n-1] v[n-1]

说明/提示

评分规则

令构造对应的最早重复时刻为 $x$，得分如下：

本地校验

题目提供 checker.cpp 和 testlib.h。

当两个文件位于同一目录时，可以使用以下命令编译检查器：

g++ checker.cpp -o checker -std=c++14

若构造答案保存在 ans.txt 中，可以使用以下命令进行检查：

checker ans.txt ans.txt ans.txt

检查器将报告构造是否合法、对应的 $x$ 值以及按评分规则计算出的得分比例。

附件下载

checker.cpp · testlib.h